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
Edward F. Schmeichel, Hajo J. Broersma, Douglas Bauer, Aurora Morgana
Publication date: 29 August 2002
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
68Q25: Analysis of algorithms and problem complexity
68R10: Graph theory (including graph drawing) in computer science
05C38: Paths and cycles
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
Related Items
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- 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