A survey on Algorithmic Aspects of Modular Decomposition

A survey on Algorithmic Aspects of Modular Decomposition 1 Michel Habib a and Christophe Paul b aLIAFA, Univ. Paris Diderot - Paris VII, France bCNRS, LIRMM, Univ. Montpellier II, France Abstract The modular decomposition is a technique that applies but is not restricted to graphs. The notion of module naturally appears in the proofs of many graph theo- retical theorems. Computing the modular decomposition tree is an important pre- processing step to solve a larger number of combinatorial optimization problems. Since the first polynomial time algorithm in the early 70's, the algorithmic of the modular decomposition has known an important development. This paper survey the ideas and techniques that arose from this line of research. Key words: Combinatorial algorithms, Graph theory, Modular decomposition 1 Introduction Modular decomposition is a technique at the crossroads of several domains of combinatorics which applies to many discrete structures such as graphs, set systems, matroids among others. As a graph decomposition technique is has been introduced by Gallai [Gal67] to study the structure of comparability graphs (those graphs whose edge set can be transitively oriented). Roughly speaking a module in graph is a subset M of vertices which share the same neighbourhood outside M . Galai showed that the family of modules of an undirected graph can be represented by a tree, the modular decomposition tree. The notion of module appeared in the litterature as closed sets [Gal67], Email addresses: habib@liafa.

• family theory


• partitive family


• families closed


• discrete structures


• recent linear


• modular decomposition


• partitive families


• overlap any