An O(n^ 2) incremental algorithm for modular decomposition of graphs and 2-structures
A module of a graph is a set of vertices that is indistinguishable from outside. I.e., every vertex outside a module is either adjacent to all vertices in the module, or is adjacent to no vertex of the module. This concept generalizes to 2-structures, which are complete graphs with an equivalence relation on the edges. The modular decomposition of a graph or 2-structure is a tree, namely the transitive reduction of the containment relation on the set of all modules. The cotree of a cograph [\textit{D. G. Corneil}, \textit{Y. Perl} and \textit{L. K. Stewart}, SIAM J. Comput. 14, 926-934 (1985; Zbl 0575.68065)] is a special form of such a decomposition tree. The modular decomposition is a linear space representation of a graph which supports efficient algorithms for problems like recognition of comparability graphs and permutation graphs. Another incremental \(O(n^2)\) algorithm computing the modular decomposition of graphs is known [\textit{J. H. Muller} and \textit{J. Spinrad}, J. Assoc. Comput. Mach. 36, No. 1, 1-19 (1989; Zbl 0671.68030)], and there are also linear time algorithms for this problem [\textit{A. Cournier} and \textit{M. Habib}, Lect. Notes Comput. Sci. 657, 212- 224 (1993)].
- Incremental modular decomposition
- Modular decomposition and transitive orientation
- An O(n2) Divide-and-Conquer Algorithm for the Prime Tree Decomposition of Two-Structures and Modular Decomposition of Graphs
- scientific article; zbMATH DE number 1456953
- Efficient and practical algorithms for sequential modular decomposition
- \(P_ 4\)-trees and substitution decomposition
- A k-structure generalization of the theory of 2-structures
- A Combinatorial Decomposition Theory
- A Fast Algorithm for the Decomposition of Graphs and Posets
- A Linear Recognition Algorithm for Cographs
- An O(n2) Divide-and-Conquer Algorithm for the Prime Tree Decomposition of Two-Structures and Modular Decomposition of Graphs
- Arborescent Structures. II: Interpretability in the Theory of Trees
- Comparability graphs and a new matroid
- Critically indecomposable partially ordered sets, graphs, tournaments and other binary relational structures
- Decomposition of Directed Graphs
- Decomposition of k-ary relations
- Graphs with unique maximal clumpings
- scientific article; zbMATH DE number 1003286 (Why is no real title available?)
- scientific article; zbMATH DE number 3859178 (Why is no real title available?)
- scientific article; zbMATH DE number 3906240 (Why is no real title available?)
- scientific article; zbMATH DE number 512932 (Why is no real title available?)
- scientific article; zbMATH DE number 3414349 (Why is no real title available?)
- Incremental construction of 2-structures
- Incremental modular decomposition
- On the X-join decomposition for undirected graphs
- Partially ordered sets and their comparability graphs
- Partitive hypergraphs
- The Recognition of Series Parallel Digraphs
- Theory of 2-structures. I: Clans, basic subclasses, and morphisms
- Theory of 2-structures. II: Representation through labeled tree families
- Transitiv orientierbare Graphen
- Dynamically maintaining split graphs
- Modular decomposition and transitive orientation
- Linear-time modular decomposition of directed graphs
- A linear algorithm to decompose inheritance graphs into modules
- The mathematics of xenology: di-cographs, symbolic ultrametrics, 2-structures and tree-representable systems of binary relations
- From modular decomposition trees to rooted median graphs
- From modular decomposition trees to level-1 networks: pseudo-cographs, polar-cats and prime polar-cats
- Special data structures for problems on graphs associated with the notion of clique or with modular decomposition
- An Algorithm for the Modular Decomposition of Hypergraphs
- An O(n2) Divide-and-Conquer Algorithm for the Prime Tree Decomposition of Two-Structures and Modular Decomposition of Graphs
- NLC\(_{2}\)-decomposition in polynomial time
- scientific article; zbMATH DE number 966717 (Why is no real title available?)
- Resolving prime modules: the structure of pseudo-cographs and galled-tree explainable graphs
- \(\boldsymbol{(\alpha, \beta )}\)-Modules in Graphs
- Approximating modular decomposition is hard
- Algorithmic aspects of switch cographs
This page was built for publication: An \(O(n^ 2)\) incremental algorithm for modular decomposition of graphs and 2-structures
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1897475)
