ICS Theory Group

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.