O(m logn) Split Decomposition of Strongly Connected Graphs

DOI10.1007/978-3-642-02029-2_16zbMath1194.05124OpenAlexW2143121874MaRDI QIDQ3655150

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

Publication date: 7 January 2010

Published in: Graph Theory, Computational Intelligence and Thought (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-02029-2_16

zbMATH Keywords

split decompositionjoin decompositionstrongly connected graphs

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) 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
• Unnamed Item
• 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 logn) Split Decomposition of Strongly Connected Graphs