<p>There is a recent survey </p>

<p>Habib and Paul (2010). <a href="http://dx.doi.org/10.1016/j.cosrev.2010.01.001">A survey of the algorithmic aspects of modular decomposition.</a> Computer Science Review 4(1): 41-59 (2010)</p>

<p>that you should check out.</p>

CC BY-SA 3.0
2011-04-14T09:09:26.970Z
2011-04-14T09:09:26.970Z
Serge Gaspers
<p>There actually <em>is</em> a (relatively) simple recursive modular decomposition algorithm that works in linear time. See: <a href="http://www.cs.utoronto.ca/~mtedder/TedderModular.pdf">http://www.cs.utoronto.ca/~mtedder/TedderModular.pdf</a></p>

CC BY-SA 3.0
2012-12-12T23:11:24.350Z
The algorithm of the paper is for undirected graphs.
Juho
CC BY-SA 4.0
2024-04-15T09:41:19.113Z
This algorithm is incorrect. We found a counterexample on 9 vertices.
Dima Pasechnik
CC BY-SA 3.0
2012-12-12T21:33:39.733Z
2012-12-12T21:33:39.733Z
Rob
<p>Philippe Gambette has a <a href="http://www.lirmm.fr/~gambette/EnsDecompositionModulaireENG.php">webpag</a>e about bibliography of modular decomposition algorithms.</p>

<p>About "A Simple Linear-Time Modular Decomposition Algorithm for Graphs, Using Order Extension", Fabien de Montgolfier provided an extended version of this paper on <a href="http://www.liafa.jussieu.fr/~fm/">his website</a>. If you are interested in variants or generalizations of MD, you can find some papers about Homogeneous Relations in his website, too.</p>

CC BY-SA 3.0
2011-04-15T01:46:04.793Z
2011-04-15T01:46:04.793Z
Abner Huang
<p>I like the <a href="http://rads.stackoverflow.com/amzn/click/0198532105" rel="nofollow">Diestel's book</a>. 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.</p>

CC BY-SA 3.0
2011-04-30T13:36:31.040Z
2011-04-30T13:36:31.040Z
dpufrj
<p>You should look at <a href="http://springerlink.metapress.com/openurl.asp?genre=article&amp;issn=0302-9743&amp;volume=3111&amp;spage=187">A Simple Linear-Time Modular Decomposition Algorithm for Graphs, Using Order Extension, SWAT 2004</a> and <a href="http://dx.doi.org/10.1016/j.dam.2004.02.017">Linear-time modular decomposition of directed graphs, Disc. Appl. Math. 2005</a> for the simplest known linear-time algorithms on undirected and directed graph respectively.</p>

<p>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").</p>

<p>FYI, the first linear-time algorithms for undirected graphs have been <a href="http://dx.doi.org/10.1007/BFb0017474">A New Linear Algorithm for Modular Decomposition. CAAP 1994</a> and <a href="http://doi.acm.org/10.1145/314464.314641">Linear-Time Modular Decomposition and Efficient Transitive Orientation of Comparability Graphs</a>.</p>

CC BY-SA 3.0
2011-04-14T04:22:29.613Z
I like "not so efficient but simpler" as a motto for doing experimental algorithms work :)
Suresh Venkat
CC BY-SA 3.0
2014-12-06T00:07:33.973Z
Author implementation http://www.liafa.jussieu.fr/~fm/algos/index.html.
mrk
CC BY-SA 3.0
2011-04-14T04:21:45.843Z
2011-04-14T04:32:42.007Z
2011-04-14T04:32:42.007Z
Gianluca Della Vedova
<p>What are good papers/books to better understand the power of Modular Decomposition and its properties?</p>

<p>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?</p>

CC BY-SA 3.0
2011-04-14T03:41:24.723Z
what is a modular decomposition ?
Suresh Venkat
CC BY-SA 3.0
2011-04-14T03:53:13.763Z
@Suresh: http://en.wikipedia.org/wiki/Modular_decomposition
David Eppstein
CC BY-SA 3.0
2011-04-14T03:58:31.180Z
@David Thanks ! I didn't know about them and they sound neat.
Suresh Venkat
CC BY-SA 3.0
2011-04-14T11:04:53.197Z
@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: http://www.liafa.jussieu.fr/~fm/algos/index.html
András Salamon
<ds.algorithms><reference-request><graph-theory><graph-algorithms>
References for Modular Decomposition
Vinicius dos Santos
# References for Modular Decomposition

(Asked by: username_0 on 2011-04-14)

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?

**Tags:** ds.algorithms, reference-request, graph-theory, graph-algorithms

> **Comments:**
> **username_1**: what is a modular decomposition ?  
> **username_2**: @Suresh: http://en.wikipedia.org/wiki/Modular_decomposition  
> **username_1**: @David Thanks ! I didn't know about them and they sound neat.  
> **username_3**: @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: http://www.liafa.jussieu.fr/~fm/algos/index.html  

---

## 5 answers

### Answer by username_10 on 2011-04-14. Score: 10 | Accepted answer

You should look at [A Simple Linear-Time Modular Decomposition Algorithm for Graphs, Using Order Extension, SWAT 2004](http://springerlink.metapress.com/openurl.asp?genre=article&issn=0302-9743&volume=3111&spage=187) and [Linear-time modular decomposition of directed graphs, Disc. Appl. Math. 2005](http://dx.doi.org/10.1016/j.dam.2004.02.017) 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](http://dx.doi.org/10.1007/BFb0017474) and [Linear-Time Modular Decomposition and Efficient Transitive Orientation of Comparability Graphs](http://doi.acm.org/10.1145/314464.314641).

> **Comments:**
> **username_1**: I like "not so efficient but simpler" as a motto for doing experimental algorithms work :)  
> **username_11**: Author implementation http://www.liafa.jussieu.fr/~fm/algos/index.html.  

---

### Answer by username_4 on 2011-04-14. Score: 17

There is a recent survey

Habib and Paul (2010). [A survey of the algorithmic aspects of modular decomposition.](http://dx.doi.org/10.1016/j.cosrev.2010.01.001) Computer Science Review 4(1): 41-59 (2010)

that you should check out.


---

### Answer by username_5 on 2012-12-12. Score: 7

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

> **Comments:**
> **username_6**: The algorithm of the paper is for undirected graphs.  
> **username_7**: This algorithm is incorrect. We found a counterexample on 9 vertices.  

---

### Answer by username_8 on 2011-04-15. Score: 7

Philippe Gambette has a [webpag](http://www.lirmm.fr/~gambette/EnsDecompositionModulaireENG.php)e 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](http://www.liafa.jussieu.fr/~fm/). If you are interested in variants or generalizations of MD, you can find some papers about Homogeneous Relations in his website, too.


---

### Answer by username_9 on 2011-04-30. Score: 0

I like the [Diestel's book](http://rads.stackoverflow.com/amzn/click/0198532105). 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.


---

