Abstract
Modular decomposition is fundamental for many important problems in algorithmic graph theory including transitive orientation, the recognition of several classes of graphs, and certain combinatorial optimization problems. Accordingly, there has been a drive towards a practical, linear-time algorithm for the problem. This paper posits such an algorithm; we present a linear-time modular decomposition algorithm that proceeds in four straightforward steps. This is achieved by introducing the notion of factorizing permutations to an earlier recursive approach. The only data structure used is an ordered list of trees, and each of the four steps amounts to simple traversals of these trees. Previous algorithms were either exceedingly complicated or resorted to impractical data-structures.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
References
Capelle, C., Habib, M., de Montgolfier, F.: Graph decompositions and factorizing permutations. Discrete Mathematics and Theoretical Computer Science 5, 55–70 (2002)
Chein, M., Habib, M., Maurer, M.C.: Partitive hypergraphs. Discrete Mathematics 37, 35–50 (1981)
Corneil, D.G., Perl, Y., Stewart, L.K.: A linear recognition algorithm for cographs. SIAM Journal of Computing 14, 926–934 (1985)
Cournier, A., Habib, M.: A new linear algorithm of modular decomposition. In: Tison, S. (ed.) CAAP 1994. LNCS, vol. 787, pp. 68–84. Springer, Heidelberg (1994)
Cowan, D.D., James, L.O., Stanton, R.G.: Graph decomposition for undirected graphs. In: 3rd S-E Conference on Combinatorics, Graph Theory and Computing, Utilitas Math., pp. 281–290 (1972)
Dahlhaus, E.: Efficient parallel algorithms for cographs and distance hereditary graphs. Discrete Applied Mathematics 57, 29–54 (1995)
Dahlhaus, E., Gustedt, J., McConnell, R.M.: Efficient and practical algorithm for sequential modular decomposition algorithm. Journal of Algorithms 41(2), 360–387 (2001)
de Figueiredo, C.M.H., Maffray, F.: Optimizing bull-free perfect graphs. SIAM J. Discret. Math. 18(2), 226–240 (2005)
Ehrenfeucht, A., Gabow, H.N., McConnell, R.M., Sullivan, S.L.: An O(n 2) divide-and-conquer algorithm for the prime tree decomposition of two-structures and modular decomposition of graphs. Journal of Algorithms 16, 283–294 (1994)
Gabow, H.N., Tarjan, R.E.: A linear-time algorithm for a special case of disjoint set union. In: STOC 1983: Proceedings of the fifteenth annual ACM symposium on Theory of computing, pp. 246–251. ACM Press, New York (1983)
Gagneur, J., Krause, R., Bouwmeester, T., Casari, G.: Modular decomposition of protein-protein interaction networks. Genome Biology 5(8), R57 (2004)
Gallai, T.: Transitiv orientierbare graphen. Acta Math. Acad. Sci. Hungar. 18, 25–66 (1967)
Habib, M., de Montgolfier, F., Paul, C.: A simple linear-time modular decomposition algorithm for graphs, using order extension. In: Hagerup, T., Katajainen, J. (eds.) SWAT 2004. LNCS, vol. 3111, pp. 187–198. Springer, Heidelberg (2004)
Habib, M., Maurer, M.C.: On the x-join decomposition of undirected graphs. Discrete Applied Mathematics 1, 201–207 (1979)
Habib, M., Paul, C., Viennot, L.: A synthesis on partition refinement: a useful routine for strings, graphs, boolean matrices and automata. In: Meinel, C., Morvan, M. (eds.) STACS 1998. LNCS, vol. 1373, pp. 25–38. Springer, Heidelberg (1998)
McConnell, R.M., Spinrad, J.: Linear-time modular decomposition and efficient transitive orientation of comparability graphs. In: 5th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 536–545 (1994)
McConnell, R.M., Spinrad, J.: Ordered vertex partitioning. Discrete Mathematics and Theoretical Computer Science 4, 45–60 (2000)
Möhring, R.H.: Algorithmic aspects of comparability graphs and interval graphs. In: Rival, I. (ed.) Graphs and Orders, pp. 41–101. D. Reidel, Boston (1985)
Möhring, R.H.: Algorithmic aspects of the substitution decomposition in optimization over relations, set systems and boolean functions. Annals of Operations Research 4, 195–225 (1985)
Möhring, R.H., Radermacher, F.J.: Substitution decomposition for discrete structures and connections with cominatorial optimization. Annals of Discrete Mathematics 19, 257–356 (1984)
Muller, J.H., Spinrad, J.: Incremental modular decomposition. Journal of the ACM 36(1), 1–19 (1989)
Papadopoulos, C., Voglis, C.: Drawing graphs using modular decomposition. In: Healy, P., Nikolov, N.S. (eds.) Graph Drawing, Limerick, Ireland, September 12-14, 2005, pp. 343–354. Springer, Heidelberg (2006)
Pnueli, A., Even, S., Lempel, A.: Transitive orientation of graphs and identification of permutation graphs. Canad. J. Math. 23, 160–175 (1971)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2008 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Tedder, M., Corneil, D., Habib, M., Paul, C. (2008). Simpler Linear-Time Modular Decomposition Via Recursive Factorizing Permutations. In: Aceto, L., Damgård, I., Goldberg, L.A., Halldórsson, M.M., Ingólfsdóttir, A., Walukiewicz, I. (eds) Automata, Languages and Programming. ICALP 2008. Lecture Notes in Computer Science, vol 5125. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-70575-8_52
Download citation
DOI: https://doi.org/10.1007/978-3-540-70575-8_52
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-70574-1
Online ISBN: 978-3-540-70575-8
eBook Packages: Computer ScienceComputer Science (R0)