Home | People | Seminar | Working Group | Conferences | Resources


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.

Return to the seminar page.

Home | People | Seminar | Working Group | Conferences | Resources

Please send comments about this page to Robert Ellis at rellis@math.tamu.edu.