# References for Modular Decomposition

What are good papers/books to better understand the power of Modular Decomposition and its properties?

I'm particularly interested in algorithmic aspects of Modular Decomposition. I have heard that it is possible to find a Modular Decomposition of a graph in linear time. Is there are an relatively simple algorithm for that? What about a not so efficient but simpler algorithm?

• what is a modular decomposition ? – Suresh Venkat Apr 14 '11 at 3:41
• – David Eppstein Apr 14 '11 at 3:53
• @David Thanks ! I didn't know about them and they sound neat. – Suresh Venkat Apr 14 '11 at 3:58
• @Nathann Cohen would probably be the best person to comment on this, since he integrated the linear-time modular decomposition algorithm into SAGE. Fabien de Montgolfier's C code: liafa.jussieu.fr/~fm/algos/index.html – András Salamon Apr 14 '11 at 11:04

You should look at A Simple Linear-Time Modular Decomposition Algorithm for Graphs, Using Order Extension, SWAT 2004 and Linear-time modular decomposition of directed graphs, Disc. Appl. Math. 2005 for the simplest known linear-time algorithms on undirected and directed graph respectively.

The problem has mainly attracted theoretical interest and the algorithms developed so far are relatively complex. I do not think that has been a sustained effort towards an algorithm that is actually amenable to be implemented (i.e. "not so efficient but simpler").

FYI, the first linear-time algorithms for undirected graphs have been A New Linear Algorithm for Modular Decomposition. CAAP 1994 and Linear-Time Modular Decomposition and Efficient Transitive Orientation of Comparability Graphs.

There is a recent survey

Habib and Paul (2010). A survey of the algorithmic aspects of modular decomposition. Computer Science Review 4(1): 41-59 (2010)

that you should check out.

Philippe Gambette has a webpage about bibliography of modular decomposition algorithms.

About "A Simple Linear-Time Modular Decomposition Algorithm for Graphs, Using Order Extension", Fabien de Montgolfier provided an extended version of this paper on his website. If you are interested in variants or generalizations of MD, you can find some papers about Homogeneous Relations in his website, too.

There actually is a (relatively) simple recursive modular decomposition algorithm that works in linear time. See: http://www.cs.utoronto.ca/~mtedder/TedderModular.pdf

• The algorithm of the paper is for undirected graphs. – Juho Dec 12 '12 at 23:11

I like the Diestel's book. It explains how modular decomposition works and how to apply it. In this book there is also a lot of information about convexity in a graph.