15
$\begingroup$

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?

Improve this question
$\endgroup$
4
  • 2
    $\begingroup$ what is a modular decomposition ? $\endgroup$
    – Suresh Venkat
    Commented Apr 14, 2011 at 3:41
  • 2
    $\begingroup$ @Suresh: en.wikipedia.org/wiki/Modular_decomposition $\endgroup$
    – David Eppstein
    Commented Apr 14, 2011 at 3:53
  • 2
    $\begingroup$ @David Thanks ! I didn't know about them and they sound neat. $\endgroup$
    – Suresh Venkat
    Commented Apr 14, 2011 at 3:58
  • 2
    $\begingroup$ @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 $\endgroup$
    – András Salamon
    Commented Apr 14, 2011 at 11:04

5 Answers 5

Reset to default
10
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • 2
    $\begingroup$ I like "not so efficient but simpler" as a motto for doing experimental algorithms work :) $\endgroup$
    – Suresh Venkat
    Commented Apr 14, 2011 at 4:22
  • $\begingroup$ Author implementation liafa.jussieu.fr/~fm/algos/index.html. $\endgroup$
    – mrk
    Commented Dec 6, 2014 at 0:07
17
$\begingroup$

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.

Improve this answer
$\endgroup$
7
$\begingroup$

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.

Improve this answer
$\endgroup$
7
$\begingroup$

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

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ The algorithm of the paper is for undirected graphs. $\endgroup$
    – Juho
    Commented Dec 12, 2012 at 23:11
  • $\begingroup$ This algorithm is incorrect. We found a counterexample on 9 vertices. $\endgroup$
    – Dima Pasechnik
    Commented Apr 15 at 9:41
0
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.