\(O(m\log n)\) split decomposition of strongly-connected graphs
type: Item
instance of: scholarly article
title: \(O(m\log n)\) split decomposition of strongly-connected graphs
zbMATH Open document ID: 1219.05139
author: Scott Lundberg
author: R. M. McConnell
author: Benson Joeris
published in: Discrete Applied Mathematics
publication date: 2010-05-25T00:00:00Z
Mathematics Subject Classification ID: 05C70
Mathematics Subject Classification ID: 05C85
zbMATH DE Number: 5711870
zbMATH Keywords: split decomposition
zbMATH Keywords: graph decomposition
zbMATH Keywords: join decomposition
MaRDI profile type: Publication
full work available at URL: j.dam.2009.10.008
OpenAlex ID: W3023454559
cites work: Distance-hereditary graphs
cites work: Digraph Decompositions and Eulerian Systems
cites work: Reducing prime graphs and recognizing circle graphs
cites work: On the extension of bipartite to parity graphs
cites work: Compositions for perfect graphs
cites work: Decomposition of Directed Graphs
cites work: Parallel Algorithms for Hierarchical Clustering and Applications to Split Decomposition and Parity Graph Recognition
cites work: Recognizing circle graphs in polynomial time
cites work: Completely separable graphs
cites work: PC trees and circular-ones arrangements.
cites work: An O(n2) Algorithm for Undirected Split Decomposition
cites work: Q3683903
cites work: Prime Testing for the Split Decomposition of a Graph
cites work: On Comparability and Permutation Graphs
cites work: Q3670598
DOI: 10.1016/J.DAM.2009.10.008
Recommended article: O(m logn) Split Decomposition of Strongly Connected Graphs
Recommended article: An O(n2) Algorithm for Undirected Split Decomposition
Recommended article: Q4228455
Recommended article: Deterministic \(\tilde O(nm)\) time edge-splitting in undirected graphs
Recommended article: Split decomposition and graph-labelled trees: characterizations and fully dynamic algorithms for totally decomposable graphs
Recommended article: The toughness of split graphs
Recommended article: Fully Decomposable Split Graphs
Recommended article: Fully decomposable split graphs
Recommended article: A simplified \(\widetilde{O}(nm)\) time edge-splitting algorithm in undirected graphs
Recommended article: On the complexity of partitioning graphs into connected subgraphs
description: scientific article; zbMATH DE number 5711870