Abstract
We present here a new algorithm linear in time and space complexity for Modular Decomposition. This algorithm relies on structural properties of prime graphs (see theorems 7, and 8), on properties of modules (see property 1 and corollary 1) but also on the cograph recognition algorithm [CPS85]. Our algorithm builds and explores the decomposition tree of any undirected graph in a depth-first search way. As a by-product we show that a vertex-splitting operation is really a central tool for modular decomposition algorithms.
Keywords
The authors wish to thank Bruno Courcelle, Hervé Dicky, Dieter Kratsch, Rolf Möhring, Stephan Olariu, Jerry Spinrad, Ross McConnel, and many others for stimulating and fruitful discussions on graph decompositions.
This is a preview of subscription content, log in via an institution.
Preview
Unable to display preview. Download preview PDF.
References
A. Cournier and M. Habib. An efficient algorithm to recognize prime undirected graphs. In E. W. Mayr, editor, Lectures notes in Computer Science, 657.Graph-Theoretic Concepts in Computer Science. 18th International Workshop, WG'92. Wiesbaden-Naurod, Germany, June 1992. Proceding, pages 212–224. Springer-Verlag, 1993.
A. Cournier and M. Habib. A new linear algorithm for modular decomposition. Raport de recherche, LIRMM, 161, Rue Ada, 34392 Montpellier Cedex 5, 1993.
M. Chein, M. Habib, and M. C. Maurer. Partitive hypergraphs. Discrete Mathematics, (37):35–50, 1981.
D. D. Cowan, L. O. James, and R. G. Stanton. Graph decomposition for undirected graphs. In R. B. Levow eds. F. Hoffman, editor, 3rd S-E Conf. Combinatorics, Graph Theory and computing, Utilitas Math, pages 281–290, Winnipeg, 1972.
A. Cournier. Sur Quelques Algorithmes de Décomposition de Graphes. PhD thesis, Université Montpellier II, 161 rue Ada, 34392 Montpellier Cedex 5, France, février 1993.
D. G. Corneil, Y. Perl, and L. K. Stewart. A linear recognition algorithm for cographs. SIAM journal of computing, (14):926–934, november 1985.
A. Ehrenfeucht and G. Rozenberg. Primitivity is hereditary for 2-structures (fundamental study). Theoretical Comp. Sci., 3(70):343–358, 1990.
A. Ehrenfeucht and G. Rozenberg. Theory of 2-structures, part i: clans, basic subclasses and morphisms (fundamental study). Theoretical Comp. Sci., 3(70):277–303, 1990.
T. Gallai. Transitiv orienterbare graphen. Acta Math. Acad. Sci. Hungar., (18):25–66, 1967. MR 36 #5026.
M. C. Golumbic. Algorithmic graph theory and perfect graphs. Academic Press, New-York, 1980.
M. Habib. Substitution des structures combinatoires, théorie et algorithmes. PhD thesis, Université Pierre et Marie Curie (Paris VI), 1981.
M. Habib, M. Huchard, and J. Spinrad. A linear algorithm to decompose inheritance graphs into modules. Rapport de Recherche CRIM-81, to appear in Algorithmica, 1990.
M. Habib and M. C. Maurer. On the x-join decomposition for undirected graphs. Discrete Applied Math, (3):198–207, 1979.
P. Ille. Indecomposable relations. preprint Université de Marseille, 1990.
P. Ille. L'ensemble des intervalles d'une multirelation binaire et réflexive. Zeitschr. f. math. Logik und Grundlagen d. Math. Bd., (37):227–256, 1991.
D. Kelly. Comparability graphs. In I. Rival, editor, Graphs and Orders, pages 3–40. D. Reidel Publishing Company, 1985.
M.C. Vilarem M. Chein, M. Habib. Hypergraphes homogènes et ensembles de parties homogènes d'un graphe ou d'un hypergraphe. C.R. Acad Sciences Paris, (287):285–287, 1978.
R. M. McConnell. A practical o(n 2) algorithm for substitution decomposition. Dept. of computer science, University of colorado at Boulder, Boulder, CO 80309 USA, 1992.
C.L. McCreary, C.L. Combs, D.H. Gill, and J.V. Warren. An automated graph drawing system using graph decomposition. In Graph Drawing'93, 1993.
R. H. Möhring. Algorithmic aspects of the substitution decomposition in optimization over relations, set systems and boolean functions. Annals of Operations Research, 6:195–225, 1985.
R. H. Möhring. Computationaly tractable classes of ordered sets. In I. Rival, editor, Algorithms and Orders, pages 105–193. Kluwer Academic Publishers, 1989. volume: 255, series C: Mathematical and Physical Sciences.
R. H. Möhring and F. J. Radermacher. Substitution decomposition for discrete structures and connections with combinatorial optimization. Ann. Discrete math, (19):257–356, 1984.
J. H. Muller and J. Spinrad. Incremental modular decomposition. Journal of the association for Computing Machinery, (1):1–19, January 1989.
R. M. McConnell and J. Spinrad. Linear-time modular decomposition and efficient transitive orientation of undirected graphs. Dept. of computer science, University of colorado at Boulder, Boulder, CO 80309 USA, 1993.
J. Sabidussi. The composition of graphs. Duke Math.Journal, (26):693–696, 1959.
L. S. Shapley. In F. Zwycky and A. Wilson, editors, New Methods of Thought and Procedure, number 26, pages 693–696. New-York, 1968.
J. Spinrad. On comparability and permutation graphs. SIAM J. COMPUT., 14(3):658–670, August 1985.
J. Spinrad. P4-trees and substitution decomposition. Discrete Applied Mathematics, (39):263–291, 1992.
J. H. Schmerl and W. T. Trotter. Critically indecomposable partially ordered sets, graphs, tournaments and other binary relational structures. preprint, 1991.
D. P. Sumner. Indecomposable graphs. PhD thesis, University of Massachussets, Amherts, 1971.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1994 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Cournier, A., Habib, M. (1994). A new linear algorithm for Modular Decomposition. In: Tison, S. (eds) Trees in Algebra and Programming — CAAP'94. CAAP 1994. Lecture Notes in Computer Science, vol 787. Springer, Berlin, Heidelberg. https://doi.org/10.1007/BFb0017474
Download citation
DOI: https://doi.org/10.1007/BFb0017474
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-57879-6
Online ISBN: 978-3-540-48373-1
eBook Packages: Springer Book Archive