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 decomposition; comparability graphs; permutation graphs; 2-structure; decomposition tree; module of a graph

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68R10: Graph theory (including graph drawing) in computer science

05C85: Graph algorithms (graph-theoretic aspects)

Related Items

Dynamically maintaining split graphs, Modular decomposition and transitive orientation, Linear-time modular decomposition of directed graphs

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