The NPO-completeness of the longest Hamiltonian cycle problem

DOI10.1016/S0020-0190(98)00003-9MaRDI QIDQ293205zbMATH OpenOpenAlexFDO

Authors Qing-Song Wu, Kun-Mao Chao, R. C. T. Lee

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) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Paths and cycles (05C38)

Recommendations

• scientific article; zbMATH DE number 3857154
• Computational complexity of the Hamiltonian cycle problem in dense hypergraphs
• On the complexity of hamiltonian path and cycle problems in certain classes of digraphs
• Complexity of the hamiltonian cycle in regular graph problem
• scientific article; zbMATH DE number 6829379
• scientific article; zbMATH DE number 4045182
• Long cycles in Hamiltonian graphs
• scientific article; zbMATH DE number 2077653
• Computing and Combinatorics
• A lower bound for the optimal crossing-free Hamiltonian cycle problem

Cites work

• scientific article; zbMATH DE number 42967 (Why is no real title available?)
• scientific article; zbMATH DE number 3566230 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 3793772 (Why is no real title available?)
• Approximate solution of NP optimization problems
• On approximating the longest path in a graph
• Optimization, approximation, and complexity classes
• P-Complete Approximation Problems

Cited in

(5)

• scientific article; zbMATH DE number 1249657 (Why is no real title available?)
• NP-completeness of the Hamming salesman problem
• Constrained sequence alignment: A general model and the hardness results
• The Hamiltonian Cycle and Travelling Salesman Problems in cP Systems
• Hamiltonian index is NP-complete

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q293205)