English version


Bibliographie d'algorithmes de décomposition modulaire

Fabien de Montgolfier avait compilé dans sa thèse et sur cette page une liste d'algorithmes de décomposition modulaire. Voici les références précises de la plupart des articles évoqués, et des liens vers les articles quand c'est possible, réunis lors de la rédaction des notes du cours de graphes de Michel Habib pour le master MPRI.

Auteurs, références Complexité Commentaires
James, Stanton, Cowan [JSC72] O(n4) premier algorithme polynomial
Maurer [Mau77] O(n4) graphes orientés
Blass [Bla78] O(n3)  
Habib, Maurer [HM79] O(n3)  
Habib [Hab81] O(n3) graphes orientés
Cunningham [Cun82] O(n3) graphes orientés
Steiner [Ste82] O(n3)  
Spinrad [Spi82] O(n2)  
Buer, Möhring [BM83] O(n3)  
Corneil, Perl, Stewart [CPS85] O(n+m) cographes
McCreary [McCreary87] O(n3)  
Muller, Spinrad [MS89] O(n2) incrémental
Adhar, Peng [AP90] O(log2 n), O(mn) proc. parallèle, cographes, CRCW-PRAM
Lin, Olariu [LO91] O(log n), O(mn) proc. parallèle, cographes, 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, incrémental
Habib, Huchard, Spinrad [HHS95] O(n+m) graphes d'héritage
McConnell [McC95] O(n2) 2-structures, incrémental
Bonizzoni, Della Vedova [BV95,BV99] O(n3k-5) hypergraphes de dimension k
Morvan, Viennot [MV96]   parallèle
Capelle, Habib [CH97] O(n+m) connaissant une permutation factorisante
Dahlhaus, Gustedt, McConnell [DGM97,DGM01] O(n+m)  
Habib, Paul, Viennot [HPV99] O(n+m log n) calcule une permutation factorisante
Uno, Yagiura [UY00] O(n) graphes de permutation, connaissant une permutation factorisante
McConnell, Spinrad [MS00] O(n+m log n)  
Habib, Paul [HP01,HP05] O(n+m log n) cographes
Capelle, Habib, Montgolfier [CHdM02] O(n+m) graphes orientés, connaissant une permutation factorisante
Dahlhaus, Gustedt, McConnell [DGM02] O(n+m) graphes orientés
Habib, Montgolfier, Paul [HdMP04] O(n+m) calcule une permutation factorisante
Shamir, Sharan [SS04] O(n+m) cographes, dynamique
McConnell, Montgolfier [MdM05] O(n+m) graphes orientés
Bergeron, Chauve, Montgolfier, Raffinot [BCMR05] O(kn) graphes de comparabilité de dimension k
Tedder, Corneil, Habib, Paul [TCHP2008] O(n+m) simple en temps linéaire


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.


A propos de ce document...

La liste des articles citées dans ce document a été compilée par Fabien de Montgolfier. Merci à Don Cowan de m'avoir transmis l'article fondateur sur le sujet ainsi que des précisions sur ses coauteurs (leur prénom).

Ce document a été généré en partie en utilisant le traducteur automatique LaTeX2HTML Version 2002-2-1 (1.70).
Il a été mis à jour le 1er avril 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.