×
Wu, Q. S.; Chao, K. M.; Lee, R. C. T.

The NPO-completeness of the longest Hamiltonian cycle problem. (English) Zbl 1338.68089

Inf. Process. Lett. 65, No. 3, 119-123 (1998).
Summary: In this paper, the longest Hamiltonian cycle problem and the longest Hamiltonian path problem are proved to be NPO-complete.

Cited in 1 Document

MSC:

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

Keywords:

computational complexity; NPO-complete; strict reduction; longest Hamiltonian cycle problem; longest traveling salesperson problem
Cite Review PDF
Full Text: DOI Link

References:

[1] Ausiello, G.; Crescenzi, P.; Protasi, M., Approximate solution of NP optimization problems, Theoret. Comput. Sci., 150, 1-55 (1995) · Zbl 0874.68145
[2] Cook, S. A., The complexity of theorem-proving procedures, (Proc. 3rd Ann. ACM Symp. on Theory of Computing (1971), ACM: ACM New York), 151-158 · Zbl 0363.68125
[3] Garey, M. R.; Johnson, D. S., (Computers and Intractability: A Guide to the Theory of NP-completeness (1979), Freeman: Freeman San Francisco, CA), 56-60 · Zbl 0411.68039
[4] Karger, D., On approximating the longest path in a graph, (Proc. 3rd Workshop on Algorithms and Data Structures (1993)), 421-432 · Zbl 1504.68171
[5] Manber, U., Introduction to Algorithms: A Creative Approach, ((1989)), 374 · Zbl 0825.68397
[6] Orponen, P.; Mannila, H., On approximation preserving reductions: Complete problems and robust measures, (Tech. Rept. C-1987-28 (1987), Department of Computer Science, University of Helsinki)
[7] Papadimitriou, C. H.; Steiglitz, K., Combinatorial Optimization: Algorithms and Complexity, ((1982)), 366-371 · Zbl 0503.90060
[8] Papadimitriou, C. H.; Yannakakis, M., Optimization approximation, and complexity classes, J. Comput. Systems Sci., 43, 425-440 (1991) · Zbl 0765.68036
[9] Sahni, S.; Gonzalez, T., P-complete approximation problems, J. ACM, 23, 555-565 (1976) · Zbl 0348.90152
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.