Problems remaining NP-complette for sparse or dense graphs

DOI10.7151/DMGT.1004MaRDI QIDQ4846683zbMATH OpenOpenAlexFDO

Authors Ingo Schiermeyer

Publication date 8 November 1995

Published in Discussiones Mathematicae Graph Theory (Search for Journal in Brave)

Full work available at URL https://doi.org/10.7151/dmgt.1004

zbMATH Keywords

computational complexityHamiltonian circuitHamiltonian pathindependent setNP-completeNP-completeness

Mathematics Subject Classification ID

Eulerian and Hamiltonian graphs (05C45) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• The edge Hamiltonian path problem is NP-complete for bipartite graphs
• scientific article; zbMATH DE number 3857154
• Hamiltonian index is NP-complete
• A note on the Hamiltonian circuit problem on directed path graphs
• Complexity of the hamiltonian cycle in regular graph problem

Cited in

(9)

• Polynomial algorithms that prove an NP-hard hypothesis implies an NP-hard conclusion
• ``Global graph problems tend to be intractable
• Improved approximation for spanning star forest in dense graphs
• Maximum independent sets near the upper bound
• scientific article; zbMATH DE number 4110112 (Why is no real title available?)
• Going far from degeneracy
• Going far from degeneracy
• Fine-grained complexity for sparse graphs
• Hamiltonian Cycle in K1,r-Free Split Graphs — A Dichotomy

This page was built for publication: Problems remaining NP-complette for sparse or dense graphs

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