Polynomial algorithms that prove an NP-hard hypothesis implies an NP-hard conclusion
type: Item
instance of: scholarly article
title: Polynomial algorithms that prove an NP-hard hypothesis implies an NP-hard conclusion
zbMATH Open document ID: 1052.68097
DOI: 10.1016/S0166-218X(01)00276-1
published in: Discrete Applied Mathematics
publication date: 2002-08-29T00:00:00Z
Mathematics Subject Classification ID: 68R10
Mathematics Subject Classification ID: 05C38
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 68Q17
zbMATH DE Number: 1792308
zbMATH Keywords: toughness
zbMATH Keywords: hamiltonian graph theory
author: D. Bauer
author: Hajo Broersma
author: Aurora Morgana
author: E. Schmeichel
MaRDI profile type: Publication
cites work: Recognizing tough graphs is NP-hard
cites work: A simple proof of a theorem of Jung
cites work: On the complexity of recognizing tough graphs
cites work: Long cycles in graphs with large degree sums
cites work: Q4350166
cites work: Q5187226
cites work: A note on Hamiltonian circuits
cites work: Q4198056
cites work: On the Structure of Non-Hamiltonian Graphs I
cites work: The NP-Completeness of Edge-Coloring
cites work: 25 pretty graph colouring problems
cites work: On Maximal Circuits in Finite Graphs
cites work: Cycle lengths and chromatic number of graphs
description: scientific article; zbMATH DE number 1792308