Splitting number is NP-complete

MaRDI QIDQ4232795zbMATH OpenFDO

Authors Luerbio Faria, Celina M. H. de Figueiredo, C. F. X. Mendonça

Publication date 23 August 1999

zbMATH Keywords

planar subgraphsplitting number

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• SPLITTING NUMBER is NP-complete
• Splitting NP-Complete Sets
• Solving some NP-complete problems using split decomposition
• scientific article; zbMATH DE number 1193306
• scientific article; zbMATH DE number 1039229
• Algorithmic approach to the split problems
• On a splitting problem
• An NP-complete number-theoretic problem
• scientific article; zbMATH DE number 4164836
• The splitting number of the complete graph

Cited in

(8)

• On the complexity of the approximation of nonplanarity parameters for cubic graphs
• Planarization and acyclic colorings of subcubic claw-free graphs
• The splitting number of the 4-cube
• scientific article; zbMATH DE number 1305502 (Why is no real title available?)
• SPLITTING NUMBER is NP-complete
• Parameterized Complexity of Vertex Splitting to Pathwidth at Most 1
• Splitting plane graphs to outerplanarity
• Parameterized complexity of vertex splitting to pathwidth at most 1

This page was built for publication: Splitting number is NP-complete

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