\(O(m\log n)\) split decomposition of strongly-connected graphs

DOI10.1016/j.dam.2009.10.008zbMath1219.05139OpenAlexW3023454559MaRDI QIDQ972339

Ross M. McConnell, Scott Lundberg, Benson L. Joeris

Publication date: 25 May 2010

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

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

zbMATH Keywords

graph decompositionsplit decompositionjoin decomposition

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85)

Cites Work

• Unnamed Item
• Unnamed Item
• Completely separable graphs
• Distance-hereditary graphs
• Reducing prime graphs and recognizing circle graphs
• On the extension of bipartite to parity graphs
• PC trees and circular-ones arrangements.
• Compositions for perfect graphs
• On Comparability and Permutation Graphs
• Digraph Decompositions and Eulerian Systems
• Decomposition of Directed Graphs
• An O(n2) Algorithm for Undirected Split Decomposition
• Parallel Algorithms for Hierarchical Clustering and Applications to Split Decomposition and Parity Graph Recognition
• Recognizing circle graphs in polynomial time
• Prime Testing for the Split Decomposition of a Graph

This page was built for publication: \(O(m\log n)\) split decomposition of strongly-connected graphs