ICS 269, Winter 1996: Theory Seminar
12 January 1996:
Modular Decomposition
George Lueker, ICS, UC Irvine
A module of a graph is a subset M of vertices such that any
vertex outside of M is either connected to all of M or none of M.
Repeatedly finding and contracting nontrivial modules produces a
modular decomposition of the graph, which can be arranged to
form a tree in which each node has a graph with vertices
corresponding to its children, and the graph at each node is either
complete, degenerate (without edges), or prime (without
nontrivial modules). The original graph can then be obtained by
expanding the tree bottom-up, blowing up the vertices at each node
into graphs coming from the corresponding subtrees.
Motivated by a recent paper [R. M. McConnel and J. P. Spinrad,
"Linear time modular decomposition and efficient transitive
orientation of comparibility graphs", 5th SODA (1994) 536-545],
George discussed applications of modular decomposition to maximum
weight independent sets, transitive orientation, and cograph
recognition, and described a method for constructing large prime
graphs.