Better approximations of non-Hamiltonian graphs

DOI10.1016/S0166-218X(97)00099-1zbMath0940.05041WikidataQ128037044 ScholiaQ128037044MaRDI QIDQ1382268

Kazuo Iwama, Eiji Miyano

Publication date: 2 June 1998

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

zbMATH Keywords

non-Hamiltonian graphsNP-ompleteness

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Eulerian and Hamiltonian graphs (05C45)

Related Items (2)

Approximation of coNP sets by NP-complete sets ⋮ A large set of non-Hamiltonian graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Recognizing tough graphs is NP-hard
• The complexity of facets (and some facets of complexity)
• The complexity of facets resolved
• Generating hard and diverse test sets for NP-hard graph problems
• Tough graphs and Hamiltonian circuits.
• On the unique satisfiability problem
• Toughness and the existence ofk-factors
• Optimal Approximations and Polynomially Levelable Sets

This page was built for publication: Better approximations of non-Hamiltonian graphs