An O(n2) Divide-and-Conquer Algorithm for the Prime Tree Decomposition of Two-Structures and Modular Decomposition of Graphs

DOI10.1006/jagm.1994.1013zbMath0797.68079OpenAlexW2027604814MaRDI QIDQ4285914

Stephen J. Sullivan, Andrzej Ehrenfeucht, Harold N. Gabow, Ross M. McConnell

Publication date: 21 April 1994

Published in: Journal of Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1006/jagm.1994.1013

zbMATH Keywords

schedulingdivide-and-conquer algorithmsubstitution decompositionprime tree decompositionmodular decomposition of graphs

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Applications of graph theory (05C90) Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20)

Related Items (22)

A \(k\)-structure generalization of the theory of 2-structures ⋮ Simple DFS on the complement of a graph and on partially complemented digraphs ⋮ An \(O(n^ 2)\) incremental algorithm for modular decomposition of graphs and 2-structures ⋮ From modular decomposition trees to level-1 networks: pseudo-cographs, polar-cats and prime polar-cats ⋮ Complete edge-colored permutation graphs ⋮ Efficient parallel modular decomposition (extended abstract) ⋮ Modular decomposition of hypergraphs ⋮ Symmetric maximal Condorcet domains ⋮ Resolving prime modules: the structure of pseudo-cographs and galled-tree explainable graphs ⋮ Modules in Robinson Spaces ⋮ Algorithmic aspects of switch cographs ⋮ Cograph editing: Merging modules is equivalent to editing P_4s ⋮ A survey of the algorithmic aspects of modular decomposition ⋮ Independent domination in finitely defined classes of graphs: polynomial algorithms ⋮ Linear-time modular decomposition of directed graphs ⋮ The mathematics of xenology: di-cographs, symbolic ultrametrics, 2-structures and tree-representable systems of binary relations ⋮ Fully dynamic algorithm for recognition and modular decomposition of permutation graphs ⋮ Algorithmic aspects of a general modular decomposition theory ⋮ From modular decomposition trees to rooted median graphs ⋮ NLC₂-DECOMPOSITION IN POLYNOMIAL TIME ⋮ Modular decomposition and transitive orientation ⋮ On Modular Decomposition Concepts: the case for Homogeneous Relations

This page was built for publication: An O(n2) Divide-and-Conquer Algorithm for the Prime Tree Decomposition of Two-Structures and Modular Decomposition of Graphs