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

DOI10.1016/J.DAM.2009.10.008MaRDI QIDQ972339zbMATH OpenOpenAlexFDO

Authors Scott Lundberg, R. M. McConnell, Benson 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

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

Recommendations

• \(O(m \log n)\) split decomposition of strongly connected graphs
• An O(n2) Algorithm for Undirected Split Decomposition
• scientific article; zbMATH DE number 1256720
• Deterministic O(nm) time edge-splitting in undirected graphs
• Split decomposition and graph-labelled trees: characterizations and fully dynamic algorithms for totally decomposable graphs
• The toughness of split graphs
• Fully decomposable split graphs
• Fully decomposable split graphs
• A simplified \(\widetilde{O}(nm)\) time edge-splitting algorithm in undirected graphs
• On the complexity of partitioning graphs into connected subgraphs

Cites work

• scientific article; zbMATH DE number 3825206 (Why is no real title available?)
• scientific article; zbMATH DE number 3906240 (Why is no real title available?)
• An O(n2) Algorithm for Undirected Split Decomposition
• Completely separable graphs
• Compositions for perfect graphs
• Decomposition of Directed Graphs
• Digraph Decompositions and Eulerian Systems
• Distance-hereditary graphs
• On Comparability and Permutation Graphs
• On the extension of bipartite to parity graphs
• PC trees and circular-ones arrangements.
• Parallel Algorithms for Hierarchical Clustering and Applications to Split Decomposition and Parity Graph Recognition
• Prime Testing for the Split Decomposition of a Graph
• Recognizing circle graphs in polynomial time
• Reducing prime graphs and recognizing circle graphs

Cited in

(2)

• A simplified \(\widetilde{O}(nm)\) time edge-splitting algorithm in undirected graphs
• \(O(m \log n)\) split decomposition of strongly connected graphs

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q972339)