\(O(m\log n)\) split decomposition of strongly-connected graphs
From MaRDI portal
Publication:972339
DOI10.1016/j.dam.2009.10.008zbMath1219.05139MaRDI 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
05C70: Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
05C85: Graph algorithms (graph-theoretic aspects)
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