Version française

Bibliography of modular decomposition algorithms

Fabien de Montgolfier had compiled in his phd thesis and on this webpage a list of modular decomposition algorithms. Here are the accurate references of the cited articles, and hyperlinks when possible.

Authors, references Complexity Comments
James, Stanton, Cowan [JSC72] O(n4) first polynomial algorithm
Maurer [Mau77] O(n4) digraphs
Blass [Bla78] O(n3)  
Habib, Maurer [HM79] O(n3)  
Habib [Hab81] O(n3) digraphs
Cunningham [Cun82] O(n3) digraphs
Steiner [Ste82] O(n3)  
Spinrad [Spi82] O(n2)  
Buer, Möhring [BM83] O(n3)  
Corneil, Perl, Stewart [CPS85] O(n+m) cographs
McCreary [McCreary87] O(n3)  
Muller, Spinrad [MS89] O(n2) incremental
Adhar, Peng [AP90] O(log2 n), O(mn) proc. parallel, cographs, CRCW-PRAM
Lin, Olariu [LO91] O(log n), O(mn) proc. parallel, cographs, EREW-PRAM
Spinrad [Spi92] O(n+mα(m,n))  
Cournier, Habib [CH93] O(n+mα(m,n))  
McConnell, Spinrad [MS94,MS97,MS99] O(n+m)  
Cournier, Habib [CH94] O(n+m)  
Ehrenfeucht, Gabow, McConnell, Sullivan [EGMS94] O(n2) 2-structures
Ehrenfeucht, Harju, Rozenberg [EHR94] O(n2) 2-structures, incremental
Habib, Huchard, Spinrad [HHS95] O(n+m) inheritance graphs
McConnell [McC95] O(n2) 2-structures, incremental
Bonizzoni, Della Vedova [BV95,BV99] O(n3k-5) hypergraphs of dimension k
Morvan, Viennot [MV96]   parallel
Capelle, Habib [CH97] O(n+m) knowing a factoring permutation
Dahlhaus, Gustedt, McConnell [DGM97,DGM01] O(n+m)  
Habib, Paul, Viennot [HPV99] O(n+m log n) compute a factoring permutation
Uno, Yagiura [UY00] O(n) permutation graphs, knowing a factoring permutation
McConnell, Spinrad [MS00] O(n+m log n)  
Habib, Paul [HP01,HP05] O(n+m log n) cographs
Capelle, Habib, Montgolfier [CHdM02] O(n+m) digraphs, knowing a factoring permutation
Dahlhaus, Gustedt, McConnell [DGM02] O(n+m) digraphs
Habib, Montgolfier, Paul [HdMP04] O(n+m) compute a factoring permutation
Shamir, Sharan [SS04] O(n+m) cographs, dynamic
McConnell, Montgolfier [MdM05] O(n+m) digraphs
Bergeron, Chauve, Montgolfier, Raffinot [BCMR05] O(kn) comparability graphs of dimension k
Tedder, Corneil, Habib, Paul [TCHP2008] O(n+m) simple linear-time


Bibliographie

AP90
Gur Saran Adhar and Shietung Peng.
Parallel algorithms for cographs and parity graphs with applications.
Journal of Algorithms, 11:252-284, 1990.

BCMR2005
Anne Bergeron, Cedric Chauve, Fabien de Montgolfier, and Matthieu Raffinot.
Computing commons interval of K permutations, with applications to modular decomposition of graphs.
In Proceedings of the thirteenth Annual European Symposium on Algorithms (ESA'05), 2005.
http://www-igm.univ-mlv.fr/~raffinot/ftp/common-interval-12-April-05.pdf.gz.

Bla78
Andreas Blass.
Graphs with unique maximal clumpings.
Journal of Graph Theory, 2(1):19-24, 1978.

BM83
Hermann Buer and Rolf H. Möhring.
A fast algorithm for the decomposition of graphs and posets.
Mathematics of Operations Research, 8:170-184, 1983.

BV95
Paola Bonizzoni and Gianluca Della Vedova.
Modular decomposition of hypergraphs.
In Proceedings of the 21st International Workshop on Graph-Theoretic Concepts in Computer Science (WG'95), volume 1017 of Lecture Notes in Computer Science, pages 303-317. Springer-Verlag, 1995.
http://dx.doi.org/10.1007/3-540-60618-1_84.

BV99
Paola Bonizzoni and Gianluca Della Vedova.
An algorithm to compute the modular decomposition of hypergraphs.
Journal of Algorithms, 32(2):65-86, 1999.
http://citeseer.ist.psu.edu/506177.html.

CH93
Alain Cournier and Michel Habib.
An efficient algorithm to recognize prime undirected graphs.
In Proceedings of the 18th International Workshop on Graph-Theoretic Concepts in Computer Science (WG'92), volume 657 of Lecture Notes in Computer Science, pages 212-224. Springer-Verlag, 1993.
http://dx.doi.org/10.1007/3-540-56402-0_49.

CH94
Alain Cournier and Michel Habib.
A new linear algorithm for modular decomposition.
In 19th International Colloquium on Trees in Algebra and Programming (CAAP'94), volume 787 of Lecture Notes in Computer Science, pages 68-84. Springer-Verlag, 1994.
http://dx.doi.org/10.1007/BFb0017474.

CH97
Christian Capelle and Michel Habib.
Graph decompositions and factorizing permutations.
In Proceedings of the fifth Israeli Symposium on the Theory of Computing and Systems (ISTCS'97), 1997.
http://citeseer.ist.psu.edu/43689.html.

CHdM02
Christian Capelle, Michel Habib, and Fabien de Montgolfier.
Graph decomposition and factorizing permutations.
Discrete Mathematics and Theoretical Computer Science, 5(1), 2002.
http://www.liafa.jussieu.fr/~fm/publications/dmtcs.ps.

CPS85
Derek G. Corneil, Yehoshua Perl, and Lorna K. Stewart.
A linear recognition algorithm for cographs.
SIAM Journal on Computing, 14(4):926-934, 1985.
http://dx.doi.org/10.1137/0214065.

Cun82
William H. Cunningham.
Decomposition of directed graphs.
SIAM Journal on Algebraic and Discrete Methods, 3(2):214-228, 1982.
http://dx.doi.org/10.1137/0603021.

DGM97
Elias Dahlhaus, Jens Gustedt, and Ross M. McConnell.
Efficient and practical modular decomposition.
In Eigth Annual ACM-SIAM Symposium On Discrete Algorithms (SODA'97), pages 26-35, 1997.
http://www.cs.colostate.edu/~rmm/DGM97.pdf.

DGM01
Elias Dahlhaus, Jens Gustedt, and Ross M. McConnell.
Efficient and practical algorithms for sequential modular decomposition.
Journal of Algorithms, 41(2):360-387, 2001.
http://www.cs.colostate.edu/~rmm/linearDecompJournal.ps.

DGM02
Elias Dahlhaus, Jens Gustedt, and Ross M. McConnell.
Partially complemented representations of digraphs.
Discrete Mathematics and Theoretical Computer Science, 5(1):147-168, 2002.
http://www.cs.colostate.edu/~rmm/cstacks.pdf.

EGMS94
Andrzej Ehrenfeucht, Harold N. Gabow, Ross M. McConnell, and Stephen J. Sullivan.
An O(n2) divide-and-conquer algorithm for the prime tree decomposition of two-structures and modular decomposition of graphs.
Journal of Algorithms, 16(2):283-294, 1994.
http://www.cs.colostate.edu/~rmm/dandc94.pdf.

EHR94
Andrzej Ehrenfeucht, Tero Harju, and Grzegorz Rozenberg.
Incremental construction of 2-structures.
Discrete Mathematics, 128(1):113-141, 1994.
http://dx.doi.org/10.1016/0012-365X(94)90107-4.

Hab81
Michel Habib.
Substitution des structures combinatoires, théorie et algorithmes.
PhD thesis, Université Pierre et Marie Curie, 1981.

HdMP04
Michel Habib, Fabien de Montgolfier, and Christophe Paul.
A simple linear-time modular decomposition algorithm for graphs, using order extension.
In Ninth Scandinavian Workshop on Algorithm Theory (SWAT'04), 2004.
http://www.liafa.jussieu.fr/~fm/publications/swat04.pdf.

HHS95
Michel Habib, Marianne Huchard, and Jeremy P. Spinrad.
A linear algorithm to decompose inheritance graphs into modules.
Algorithmica, 13:573-591, 1995.
http://www.springerlink.com/index/V3384M611187NL12.pdf.

HM79
Michel Habib and Marie-Catherine Maurer.
On the X-Join decomposition for undirected graphs.
Discrete Applied Mathematics, 3:201-207, 1979.
http://dx.doi.org/10.1016/0166-218X(79)90043-X.

HP01
Michel Habib and Christophe Paul.
A simple linear time algorithm for cograph recognition.
http://citeseer.ist.psu.edu/habib01simple.html, 2001.

HP05
Michel Habib and Christophe Paul.
A simple linear time algorithm for cograph recognition.
Discrete Applied Mathematics, 145(2):183-197, 2005.
http://dx.doi.org/10.1016/j.dam.2004.01.011.

HPV99
Michel Habib, Christophe Paul, and Laurent Viennot.
Partition refinement techniques: an interesting algorithmic toolkit.
International Journal of Foundations of Computer Science, 10(2):147-170, 1999.
http://gyroweb.inria.fr/~viennot/postscripts/ijfcs00.ps.gz.

JSC72
Lee O. James, Ralph G. Stanton, and Donald D. Cowan.
Graph decomposition for undirected graphs.
In F. Hoffman, editor, Proceedings of the third Southeastern International Conference on Combinatorics, Graph Theory, and Computing (CGTC'72), pages 281-290. R. B. Levow eds., 1972.

LO91
Rong Lin and Stephan Olariu.
An NC recognition algorithm for cographs.
Journal of Parallel and Distributed Computing, 13(1):76-90, 1991.
http://dx.doi.org/10.1016/0743-7315(91)90111-L.

Mau77
Marie-Catherine Maurer.
Joints et décompositions premières dans les graphes.
PhD thesis, Université Pierre et Marie Curie (Paris VI), 1977.

McC95
Ross M. McConnell.
An O(n2) incremental algorithm for modular decomposition of graphs and 2-structures.
Algorithmica, 14:209-227, 1995.
http://www.cs.colostate.edu/~rmm/incralg.pdf.

MdM05
Ross M. McConnell and Fabien de Montgolfier.
Linear-time modular decomposition of directed graphs.
Discrete Applied Mathematics, 2(145):189-209, 2005.
http://www.cs.colostate.edu/~rmm/digraphDecomp.pdf.

MS94
Ross M. McConnell and Jeremy P. Spinrad.
Linear-time modular decomposition and efficient transitive orientation of comparability graphs.
In Proceedings of the Fifth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'94), pages 536-545, 1994.
http://www.cs.colostate.edu/~rmm/linModDecomp.pdf.

MS97
Ross M. McConnell and Jeremy P. Spinrad.
Linear-time transitive orientation.
In Eigth Annual ACM-SIAM Symposium On Discrete Algorithms (SODA'97), 1997.
http://www.cs.colostate.edu/~rmm/linTOSODA.pdf.

MS99
Ross M. McConnell and Jeremy P. Spinrad.
Modular decomposition and transitive orientation.
Discrete Mathematics, 201:189-241, 1999.
http://www.cs.colostate.edu/~rmm/linto.pdf.

MS00
Ross M. McConnell and Jeremy P. Spinrad.
Ordered vertex partitioning.
Discrete Mathematics and Theoretical Computer Science, 4:45-60, 2000.
http://www.cs.colostate.edu/~rmm/dm040104.pdf.

McCreary1987
Carolyn L. McCreary.
An algorithm for parsing a graph grammar.
PhD thesis, University of Colorado, 1987.

MV96
Michel Morvan and Laurent Viennot.
Parallel comparability graph recognition and modular decomposition.
In Proceedings of the thirteenth Annual Symposium on Theoretical Aspects of Computer Science (STACS'96), volume 1046 of Lecture Notes in Computer Science, pages 169-180. Springer-Verlag, 1996.
http://www.liafa.jussieu.fr/web9/rapportrech/rapportsWeb/1995/stacs96.pdf.

MS89
John H. Muller and Jeremy P. Spinrad.
Incremental modular decomposition.
Journal of the ACM, 36.1:1-19, 1989.
http://dx.doi.org/10.1145/58562.59300.

Spi82
Jeremy P. Spinrad.
Two-dimensional partial orders.
PhD thesis, Princeton University, 1982.

Spi92
Jeremy P. Spinrad.
P4-trees and substitution decomposition.
Discrete Applied Mathematics, 39:263-291, 1992.
http://dx.doi.org/10.1016/0166-218X(92)90180-I.

SS04
Ron Shamir and Roded Sharan.
A fully-dynamic algorithm for modular decomposition and recognition of cographs.
Discrete Applied Mathematics, 136(2-3):329-340, 2004.
http://www.math.tau.ac.il/~rshamir/papers/dcog_DAM.ps.

Ste82
George Steiner.
Machine scheduling with precedence constraints.
PhD thesis, Department of Combinatorics and Optimization, University of Waterloo, 1982.

TCHP2008
Marc Tedder and Derek Corneil and Michel Habib and Christophe Paul
Simpler Linear-Time Modular Decomposition Via Recursive Factorizing Permutations.
Proceedings of the 35th International Colloquium on Automata, Languages and Programming (ICALP'08), volume 5125 of Lecture Notes in Computer Science, pages 634-645. Springer-Verlag, 2008.
http://dx.doi.org/10.1007/978-3-540-70575-8_52 (see also http://arxiv.org/abs/0710.3901).

UY00
Takeaki Uno and Mutsunori Yagiura.
Fast algorithms to enumerate all common intervals of two permutations.
Algorithmica, 14:209-227, 2000.
http://citeseer.ist.psu.edu/uno00fast.html.


About this document...

The list of articles cited in this documents was compiled mostly by Fabien de Montgolfier. Thanks to Don Cowan for sending me the historical article on the subject as well as information on their coauthors (first names).

This document was partly generated using the LaTeX2HTML automatic translator Version 2002-2-1 (1.70).
It was updated on April 1st, 2009.

Copyright © 1993, 1994, 1995, 1996, Nikos Drakos, Computer Based Learning Unit, University of Leeds.
Copyright © 1997, 1998, 1999, Ross Moore, Mathematics Department, Macquarie University, Sydney.