Polynomial algorithms that prove an NP-hard hypothesis implies an NP-hard conclusion

DOI10.1016/S0166-218X(01)00276-1MaRDI QIDQ1613360zbMATH OpenFDO

Authors D. Bauer, Hajo Broersma, Aurora Morgana, E. Schmeichel

Publication date 29 August 2002

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

zbMATH Keywords

toughnesshamiltonian graph theory

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Paths and cycles (05C38)

Recommendations

• scientific article; zbMATH DE number 2077653
• Problems remaining NP-complette for sparse or dense graphs
• scientific article; zbMATH DE number 4075117
• Extensions and consequences of Chvátal-Erdös' theorem
• Thomassen's conjecture implies polynomiality of 1-Hamilton-connectedness in line graphs

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1055145 (Why is no real title available?)
• scientific article; zbMATH DE number 3895002 (Why is no real title available?)
• 25 pretty graph colouring problems
• A note on Hamiltonian circuits
• A simple proof of a theorem of Jung
• Cycle lengths and chromatic number of graphs
• Long cycles in graphs with large degree sums
• On Maximal Circuits in Finite Graphs
• On the Structure of Non-Hamiltonian Graphs I
• On the complexity of recognizing tough graphs
• Recognizing tough graphs is NP-hard
• The NP-Completeness of Edge-Coloring

Cited in

(6)

• scientific article; zbMATH DE number 2230266 (Why is no real title available?)
• Nonconstructive tools for proving polynomial-time decidability
• On one extension of Dirac's theorem on Hamiltonicity
• Toughness in graphs -- a survey
• Proof Complexity Modulo the Polynomial Hierarchy: Understanding Alternation as a Source of Hardness
• scientific article; zbMATH DE number 218550 (Why is no real title available?)

This page was built for publication: Polynomial algorithms that prove an NP-hard hypothesis implies an NP-hard conclusion

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