I am trying to learn how to find modular decomposition of graph using the method given in the paper Simpler Linear-Time Modular Decomposition via Recursive Factorizing Permutations. I am unable to understand the method properly which is given in the paper. Can some one explain the procedure to find the modular decomposition of graph with example using the procedure given in this paper [ or using any other simpler algorithm available in literature ]

Thank you.

  • 1
    $\begingroup$ The conference version (as always) is very short and lacks many crucial details. If I remember correctly, the journal version has been finished (and accepted somewhere?), so you may ask the authors to get a copy. BTW, the first author managed to implement the algorithm and has the codes free to get (cs.toronto.edu/~mtedder). Warning: I tested the codes back in 2010, and found some small bug, which I've reported to the author and should have been fixed. But I didn't follow since then. $\endgroup$
    – Yixin Cao
    Commented Aug 2, 2014 at 7:47
  • 1
    $\begingroup$ There is also an implementation of a modular decomposition algorithm (liafa.jussieu.fr/~fm/algos/index.html) in Sage (sagemath.org/doc/reference/graphs/sage/graphs/…) but at the moment it prints warnings when it is used as it is known to return wrong answers from time to time. I reported the bug but the original source code is not totally fixed yet :-/ $\endgroup$ Commented Aug 2, 2014 at 10:49
  • $\begingroup$ note wikipedia also has some info/ refs. this question refs for modular decomposition also seem similar $\endgroup$
    – vzn
    Commented Aug 2, 2014 at 15:08


Your Answer

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

Browse other questions tagged or ask your own question.