Deconstructing a Graph

Anne Berry
LIRMM, Montpellier, France

We extend to an arbitrary graph the notion of leaf in a tree, as well as the decomposition by its articulation points. In order to do this, we define the concept of moplex, which is a generalization of a leaf, and study the corresponding "leaf-shedding" process. We then go on to present the decomposition of a graph by its minimal separators, introducing a technique which forces the presence of an articulation clique by a local modification. We explain how this process preserves strong invariants which ensure the coherence of our decomposition.

Back to seminar homepage