Incremental modular decomposition
- 1 January 1989
- journal article
- Published by Association for Computing Machinery (ACM) in Journal of the ACM
- Vol. 36 (1) , 1-19
- https://doi.org/10.1145/58562.59300
Abstract
Modular decomposition is a form of graph decomposition that has been discovered independently by researchers in graph theory, game theory, network theory, and other areas. This paper reduces the time needed to find the modular decomposition of a graph from Ω( n 3 ) to Ο( n 2 ). Together with a new algorithm for transitive orientation given in [21], this leads to fast new algorithms for a number of problems in graph recognition and isomorphism, including recognition of comparability graphs and permutation graphs. The new algorithm works by inserting each vertex successively into the decomposition tree, using Ο( n ) time to insert each vertex.Keywords
This publication has 12 references indexed in Scilit:
- Recognition and isomorphism of two dimensional partial ordersPublished by Springer Nature ,2005
- A Linear Recognition Algorithm for CographsSIAM Journal on Computing, 1985
- Algorithmic Aspects of Comparability Graphs and Interval GraphsPublished by Springer Nature ,1985
- Decomposition of Directed GraphsSIAM Journal on Algebraic Discrete Methods, 1982
- On testing isomorphism of permutation graphsNetworks, 1981
- On the X-join decomposition for undirected graphsDiscrete Applied Mathematics, 1979
- Graphs with unique maximal clumpingsJournal of Graph Theory, 1978
- Transitiv orientierbare GraphenActa Mathematica Hungarica, 1967
- On CommitteesPublished by Springer Nature ,1967
- Graph derivativesMathematische Zeitschrift, 1961