Tutte seminar - Bill Cunningham

Split Decomposition

Abstract:

The split decomposition of undirected graphs (also called join decomposition) has a number of nice applications. There are also attractive results on unique decomposition and on the structure of indecomposable graphs, and efficient decomposition algorithms. I will survey some of this. I will also describe some of what is known (and not known) about more general decompositions and more general contexts, such as digraphs, hypergraphs, and matroids.