3

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.

Kumar
  • 2,044
  • 13
  • 27
  • 1
    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 (http://www.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. – Yixin Cao Aug 02 '14 at 07:47
  • 1
    There is also an implementation of a modular decomposition algorithm (http://www.liafa.jussieu.fr/~fm/algos/index.html) in Sage (http://www.sagemath.org/doc/reference/graphs/sage/graphs/modular_decomposition/modular_decomposition.html) 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 :-/ – Nathann Cohen Aug 02 '14 at 10:49
  • note wikipedia also has some info/ refs. this question refs for modular decomposition also seem similar – vzn Aug 02 '14 at 15:08

0 Answers0