Linear-time modular decomposition of directed graphs

DOI10.1016/j.dam.2004.02.017zbMath1055.05123OpenAlexW2008160316WikidataQ56766713 ScholiaQ56766713MaRDI QIDQ1764805

Ross M. McConnell, Fabien de Montgolfier

Publication date: 22 February 2005

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2004.02.017

zbMATH Keywords

linear-time algorithms2-structuresModular decompositionTournamentsDirected graphsPartitive familiesTree-decomposable families

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Directed graphs (digraphs), tournaments (05C20)

Related Items (17)

Hierarchical and modularly-minimal vertex colorings ⋮ Parameterized complexity of the list coloring reconfiguration problem with graph parameters ⋮ Deterministic Algorithms for the Independent Feedback Vertex Set Problem ⋮ A general algorithmic scheme for combinatorial decompositions with application to modular decompositions of hypergraphs ⋮ A graph isomorphism condition and equivalence of reaction systems ⋮ Decomposition tree of a lexicographic product of binary structures ⋮ Generalized Fitch graphs. II: Sets of binary relations that are explained by edge-labeled trees ⋮ Kernels for feedback arc set in tournaments ⋮ Generalising submodularity and Horn clauses: Tractable optimization problems defined by tournament pair multimorphisms ⋮ A distance measure for large graphs based on prime graphs ⋮ The mathematics of xenology: di-cographs, symbolic ultrametrics, 2-structures and tree-representable systems of binary relations ⋮ Reconstructing gene trees from Fitch's xenology relation ⋮ SIMPLE EXTENSIONS OF COMBINATORIAL STRUCTURES ⋮ Algorithmic aspects of a general modular decomposition theory ⋮ \(k\)-majority digraphs and the hardness of voting with a constant number of voters ⋮ Parameterized Complexity of the List Coloring Reconfiguration Problem with Graph Parameters ⋮ Tournaments without acyclic interval.

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Theory of 2-structures. I: Clans, basic subclasses, and morphisms
• Theory of 2-structures. II: Representation through labeled tree families
• Complement reducible graphs
• Partitive hypergraphs
• \(P_ 4\)-trees and substitution decomposition
• Modular decomposition and transitive orientation
• Recognizing interval digraphs and interval bigraphs in polynomial time
• An \(O(n^ 2)\) incremental algorithm for modular decomposition of graphs and 2-structures
• Efficient and Practical Algorithms for Sequential Modular Decomposition
• P₄-Reducible Graphs-Class of Uniquely Tree-Representable Graphs
• Three Partition Refinement Algorithms
• Graph Classes: A Survey
• An O(n2) Divide-and-Conquer Algorithm for the Prime Tree Decomposition of Two-Structures and Modular Decomposition of Graphs
• Parallel Algorithms for Hierarchical Clustering and Applications to Split Decomposition and Parity Graph Recognition
• Transitiv orientierbare Graphen

This page was built for publication: Linear-time modular decomposition of directed graphs