An O(n2) Algorithm for Undirected Split Decomposition

DOI10.1006/jagm.1994.1007zbMath0803.68092OpenAlexW1987650805MaRDI QIDQ4289844

Tze-Heng Ma, Jeremy P. Spinrad

Publication date: 24 May 1994

Published in: Journal of Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1006/jagm.1994.1007

zbMATH Keywords

time complexityjoin decompositionundirected split decomposition

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Graph theory (05C99)

Related Items (14)

Detecting 2-joins faster ⋮ On polygon numbers of circle graphs and distance hereditary graphs ⋮ Reduced clique graphs of chordal graphs ⋮ Split decomposition and graph-labelled trees: characterizations and fully dynamic algorithms for totally decomposable graphs ⋮ Polynomial-time recognition of clique-width \(\leq 3\) graphs ⋮ On the (non-)existence of polynomial kernels for \(P _{l }\)-free edge modification problems ⋮ Practical and efficient circle graph recognition ⋮ Practical and efficient split decomposition via graph-labelled trees ⋮ Solving some NP-complete problems using split decomposition ⋮ Polynomial-time algorithm for isomorphism of graphs with clique-width at most three ⋮ \(O(m\log n)\) split decomposition of strongly-connected graphs ⋮ Circle graphs and the cycle double cover conjecture ⋮ O(m logn) Split Decomposition of Strongly Connected Graphs ⋮ Algorithms for maximum weight induced paths

This page was built for publication: An O(n2) Algorithm for Undirected Split Decomposition