The NPO-completeness of the longest Hamiltonian cycle problem

DOI10.1016/S0020-0190(98)00003-9zbMath1338.68089OpenAlexW2031264473MaRDI QIDQ293205

F. Blanchet-Sadri, M. Dambrine

Publication date: 9 June 2016

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: http://www.sciencedirect.com/science/article/pii/S0020019098000039?np=y

zbMATH Keywords

computational complexitylongest Hamiltonian cycle problemlongest traveling salesperson problemNPO-completestrict reduction

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Paths and cycles (05C38) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (1)

Constrained sequence alignment: A general model and the hardness results

Cites Work

• Approximate solution of NP optimization problems
• Optimization, approximation, and complexity classes
• P-Complete Approximation Problems
• On approximating the longest path in a graph
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: The NPO-completeness of the longest Hamiltonian cycle problem