Prime Testing for the Split Decomposition of a Graph

DOI10.1137/0402051MaRDI QIDQ4729358zbMATH OpenOpenAlexFDO

Authors Jeremy P. Spinrad

Publication date 1989

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/0402051

zbMATH Keywords

graph decompositionjoin decompositionsplit decomposition

Mathematics Subject Classification ID

Graph theory (05C99) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• An O(n2) Algorithm for Undirected Split Decomposition
• scientific article; zbMATH DE number 3977053
• Practical and efficient split decomposition via graph-labelled trees
• scientific article; zbMATH DE number 1456953
• An O(n2) Divide-and-Conquer Algorithm for the Prime Tree Decomposition of Two-Structures and Modular Decomposition of Graphs

Cited in

(11)

• A decomposition for a class of \((P_ 5,\overline{P}_ 5)\)-free graphs
• On graphs without \(P_ 5\) and \(\overline {P}_ 5\)
• Fully decomposable split graphs
• Rank connectivity and pivot-minors of graphs
• Linear time split decomposition revisited
• Fully decomposable split graphs
• O(m n) split decomposition of strongly connected graphs
• An O(n2) Algorithm for Undirected Split Decomposition
• Graph-Theoretic Concepts in Computer Science
• A new algorithm for decomposition of graphical models
• \(O(m\log n)\) split decomposition of strongly-connected graphs

This page was built for publication: Prime Testing for the Split Decomposition of a Graph

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4729358)