Event Detail

Event Type: 
Geometry-Topology Seminar
Monday, April 27, 2020 - 12:00 to 12:50

Speaker Info

Graduate Student - Computer Science

The treewidth of a graph is the size of the smallest tree decomposition of the
graph. Intuitively, a graph with small treewidth looks like a tree. Tree decom-
positions are used in faster algorithms for problems on graphs with bounded
treewidth that are hard otherwise. While algorithmic problems for bounded
treewidth graphs have been well studied, there has been little work on problems
for simplicial complexes with bounded treewidth 1-skeleton
In this talk, we introduce the notion of tree decompositions and treewidth of
graphs. we then show how we can design algorithms on tree decompositions of
the 1-skeleton of simplicial complexes. If the size of these tree decompositions
is bounded, these algorithms run in polynomial time. In particular, we present
algorithms for the minimum bounded chain problem and the problem of nding
a predetermined surface within a 2-complex with bounded treewidth 1-skeleton.
Strong hardness results exists for both of these problems in their general form.