The NPO-completeness of the longest Hamiltonian cycle problem

被引：1
|
作者：
Wu, QS
Chao, KM
Lee, RCT [1 ]
机构：
[1] Providence Univ, Dept Comp Sci, Taichung 43309, Taiwan
[2] Natl Tsing Hua Univ, Dept Comp Sci, Hsinchu 30043, Taiwan
来源：
INFORMATION PROCESSING LETTERS | 1998年 / 65卷 / 03期
关键词：
computational complexity; NPO-complete; strict reduction; longest Hamiltonian cycle problem; longest traveling salesperson problem;
D O I：
10.1016/S0020-0190(98)00003-9
中图分类号：
TP [自动化技术、计算机技术];
学科分类号：
0812 ;
摘要：
In this paper, the longest Hamiltonian cycle problem and the longest Hamiltonian path problem are proved to be NPO-complete. (C) 1998 Published by Elsevier Science B.V.
引用
收藏
页码：119 / 123
页数：5
相关论文
共 13 条
12