An O(n2) Algorithm for Undirected Split Decomposition

DOI10.1006/JAGM.1994.1007MaRDI QIDQ4289844zbMATH OpenOpenAlexFDO

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

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)

Recommendations

• Prime Testing for the Split Decomposition of a Graph
• Linear time split decomposition revisited
• Practical and efficient split decomposition via graph-labelled trees
• \(O(m \log n)\) split decomposition of strongly connected graphs
• \(O(m\log n)\) split decomposition of strongly-connected graphs

Cited in

(18)

• scientific article; zbMATH DE number 1420903 (Why is no real title available?)
• Practical and efficient split decomposition via graph-labelled trees
• On polygon numbers of circle graphs and distance hereditary graphs
• A simplified \(\widetilde{O}(nm)\) time edge-splitting algorithm in undirected graphs
• Linear time split decomposition revisited
• \(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
• Circle graphs and the cycle double cover conjecture
• Solving some NP-complete problems using split decomposition
• Detecting 2-joins faster
• Prime Testing for the Split Decomposition of a Graph
• Efficient splitting and merging algorithms for order decomposable problems.
• On the (non-)existence of polynomial kernels for \(P _{l }\)-free edge modification problems
• \(O(m\log n)\) split decomposition of strongly-connected graphs
• Algorithms for maximum weight induced paths
• Reduced clique graphs of chordal graphs
• Practical and efficient circle graph recognition

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)