An O(n2) Algorithm for Undirected Split Decomposition
From MaRDI portal
Publication:4289844
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
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
