Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

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?

share|improve this question
2  
what is a modular decomposition ? –  Suresh Venkat Apr 14 '11 at 3:41
2  
1  
@David Thanks ! I didn't know about them and they sound neat. –  Suresh Venkat Apr 14 '11 at 3:58
2  
@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

5 Answers 5

up vote 10 down vote accepted

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.

share|improve this answer
2  
I like "not so efficient but simpler" as a motto for doing experimental algorithms work :) –  Suresh Venkat Apr 14 '11 at 4:22

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.

share|improve this answer

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.

share|improve this answer

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

share|improve this answer
1  
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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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