An \(O(n^ 2)\) incremental algorithm for modular decomposition of graphs and 2-structures

DOI10.1007/BF01206330zbMath0827.05056MaRDI QIDQ1897475

Ross M. McConnell

Publication date: 27 November 1995

Published in: Algorithmica (Search for Journal in Brave)

zbMATH Keywords

modular decompositioncomparability graphspermutation graphs2-structuredecomposition treemodule of a graph

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (7)

From modular decomposition trees to level-1 networks: pseudo-cographs, polar-cats and prime polar-cats ⋮ Linear-time modular decomposition of directed graphs ⋮ The mathematics of xenology: di-cographs, symbolic ultrametrics, 2-structures and tree-representable systems of binary relations ⋮ Dynamically maintaining split graphs ⋮ From modular decomposition trees to rooted median graphs ⋮ NLC₂-DECOMPOSITION IN POLYNOMIAL TIME ⋮ Modular decomposition and transitive orientation

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Decomposition of k-ary relations
• Theory of 2-structures. I: Clans, basic subclasses, and morphisms
• Theory of 2-structures. II: Representation through labeled tree families
• On the X-join decomposition for undirected graphs
• Partitive hypergraphs
• \(P_ 4\)-trees and substitution decomposition
• Comparability graphs and a new matroid
• Incremental construction of 2-structures
• A \(k\)-structure generalization of the theory of 2-structures
• Critically indecomposable partially ordered sets, graphs, tournaments and other binary relational structures
• Partially ordered sets and their comparability graphs
• A Fast Algorithm for the Decomposition of Graphs and Posets
• A Linear Recognition Algorithm for Cographs
• Incremental modular decomposition
• A Combinatorial Decomposition Theory
• Arborescent Structures. II: Interpretability in the Theory of Trees
• The Recognition of Series Parallel Digraphs
• Decomposition of Directed Graphs
• Graphs with unique maximal clumpings
• An O(n2) Divide-and-Conquer Algorithm for the Prime Tree Decomposition of Two-Structures and Modular Decomposition of Graphs
• Transitiv orientierbare Graphen

This page was built for publication: An \(O(n^ 2)\) incremental algorithm for modular decomposition of graphs and 2-structures