Polynomial algorithms that prove an NP-hard hypothesis implies an NP-hard conclusion
DOI10.1016/S0166-218X(01)00276-1zbMATH Open1052.68097MaRDI QIDQ1613360FDOQ1613360
Authors: D. Bauer, Hajo Broersma, Aurora Morgana, E. Schmeichel 
Publication date: 29 August 2002
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Recommendations
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)
Cites Work
- Title not available (Why is that?)
- Title not available (Why is that?)
- The NP-Completeness of Edge-Coloring
- Title not available (Why is that?)
- A note on Hamiltonian circuits
- 25 pretty graph colouring problems
- Cycle lengths and chromatic number of graphs
- On Maximal Circuits in Finite Graphs
- Long cycles in graphs with large degree sums
- Recognizing tough graphs is NP-hard
- A simple proof of a theorem of Jung
- On the complexity of recognizing tough graphs
- On the Structure of Non-Hamiltonian Graphs I
Cited In (6)
- Toughness in graphs -- a survey
- Title not available (Why is that?)
- Proof Complexity Modulo the Polynomial Hierarchy: Understanding Alternation as a Source of Hardness
- On one extension of Dirac's theorem on Hamiltonicity
- Nonconstructive tools for proving polynomial-time decidability
- Title not available (Why is that?)
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)
