Speaker:
Illya Hicks, (Department of Industrial Engineering, Texas A&M University)
Title:
The Branchwidth of Graphs and Cycle Matroids
Abstract:
This talk is given in two parts. The first part talks about research in
computing optimal branch decompositions for connected graphs using a
branch-decomposition-based algorithm. The second part of the talks covers a
result showing that for a graph with a cycle of at least length 2 then the
branchwidth of the graph is equivalent to the branchwidth of its cycle
matroid. The notions of branch decompositions and branchwidth were
introduced by Robertson and Seymour in their proof of the graph minors
theorem. Branch decompositions are also of algorithmic importance because
of their appeal to solve intractable problems modeled on graphs with bounded
branchwidth.
|