SPLITTING NUMBER is NP-complete

DOI10.1016/S0166-218X(00)00220-1MaRDI QIDQ5928869zbMATH OpenWikidataFDO

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

Publication date 7 October 2001

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/S0166-218X(00)00220-1

zbMATH Keywords

PLANAR SUBGRAPHSPLITTING NUMBER

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• scientific article; zbMATH DE number 1262805
• 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

Cites work

• Edge-Deletion Problems
• Efficient Planarity Testing
• scientific article; zbMATH DE number 1189238 (Why is no real title available?)
• scientific article; zbMATH DE number 3668651 (Why is no real title available?)
• Planarizing graphs---a survey and annotated bibliography
• The complexity of theorem-proving procedures
• The splitting number of complete bipartite graphs
• The splitting number of the complete graph

Cited in

(14)

• On the complexity of the approximation of nonplanarity parameters for cubic graphs
• Boundary graph classes for some maximum induced subgraph problems
• On maximum planar induced subgraphs
• scientific article; zbMATH DE number 1189238 (Why is no real title available?)
• scientific article; zbMATH DE number 1262805 (Why is no real title available?)
• scientific article; zbMATH DE number 1305502 (Why is no real title available?)
• scientific article; zbMATH DE number 2230213 (Why is no real title available?)
• Splitting plane graphs to outerplanarity
• Planarizing graphs and their drawings by vertex splitting
• An FPT algorithm for bipartite vertex splitting
• Splitting plane graphs to outerplanarity
• The complexity of cluster vertex splitting and company
• On the complexity of establishing hereditary graph properties via vertex splitting
• A unified FPT framework for crossing number problems

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 Q5928869)