Polynomial algorithms that prove an NP-hard hypothesis implies an NP-hard conclusion
From MaRDI portal
Publication:1613360
DOI10.1016/S0166-218X(01)00276-1zbMath1052.68097MaRDI QIDQ1613360
Douglas Bauer, Aurora Morgana, Hajo J. Broersma, Edward F. Schmeichel
Publication date: 29 August 2002
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Paths and cycles (05C38) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items (3)
On one extension of Dirac's theorem on Hamiltonicity ⋮ Toughness in graphs -- a survey ⋮ Unnamed Item
Cites Work
- 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
- Cycle lengths and chromatic number of graphs
- A note on Hamiltonian circuits
- The NP-Completeness of Edge-Coloring
- On Maximal Circuits in Finite Graphs
- On the Structure of Non-Hamiltonian Graphs I
- 25 pretty graph colouring problems
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: Polynomial algorithms that prove an NP-hard hypothesis implies an NP-hard conclusion
