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

DOI10.1016/J.DAM.2009.10.008zbMATH Open1219.05139OpenAlexW3023454559MaRDI QIDQ972339FDOQ972339

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

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 \(\tilde 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

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)

Cites Work

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

Cited In (2)

• \(O(m \log n)\) split decomposition of strongly connected graphs
• A simplified \(\widetilde{O}(nm)\) time edge-splitting algorithm in undirected 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)