An O(n2) Algorithm for Undirected Split Decomposition
From MaRDI portal
Publication:4289844
DOI10.1006/JAGM.1994.1007zbMATH Open0803.68092OpenAlexW1987650805MaRDI QIDQ4289844FDOQ4289844
Authors: 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
Recommendations
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Graph theory (05C99)
Cited In (18)
- Title not available (Why is that?)
- Detecting 2-joins faster
- \(O(m\log n)\) split decomposition of strongly-connected graphs
- Polynomial-time recognition of clique-width \(\leq 3\) graphs
- Split decomposition and graph-labelled trees: characterizations and fully dynamic algorithms for totally decomposable graphs
- On the (non-)existence of polynomial kernels for \(P _{l }\)-free edge modification problems
- \(O(m \log n)\) split decomposition of strongly connected graphs
- Reduced clique graphs of chordal graphs
- A simplified \(\widetilde{O}(nm)\) time edge-splitting algorithm in undirected graphs
- Efficient splitting and merging algorithms for order decomposable problems.
- Solving some NP-complete problems using split decomposition
- Practical and efficient split decomposition via graph-labelled trees
- Circle graphs and the cycle double cover conjecture
- Practical and efficient circle graph recognition
- Algorithms for maximum weight induced paths
- On polygon numbers of circle graphs and distance hereditary graphs
- Prime Testing for the Split Decomposition of a Graph
- Linear time split decomposition revisited
This page was built for publication: An O(n2) Algorithm for Undirected Split Decomposition
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4289844)
