ADJACENCY RELATION ON TRAVELING SALESMAN POLYTOPE IS NP-COMPLETE

被引：41

作者：

PAPADIMITRIOU, CH

机构：

来源：

关键词：

D O I：

10.1007/BF01588973

中图分类号：

TP31 [计算机软件];

学科分类号：

081202 ; 0835 ;

摘要：

引用

页码：312 / 324

页数：13

共 24 条

[1]

Aho A. V., 1974, DESIGN ANAL COMPUTER

[2] FACETS OF KNAPSACK POLYTOPE [J].

BALAS, E .

[3] TRAVELING SALESMAN PROBLEM - A SURVEY [J].

BELLMORE, M ;

NEHAUSE.GL .

[4] CERTAIN POLYTOPES ASSOCIATED WITH GRAPHS [J].

CHVATAL, V .

[5]

Edmonds J., 1971, MATH PROGRAM, V1, P127, DOI [10.1007/BF01584082, DOI 10.1007/BF01584082]

[6]

Garey M. R., 1976, SIAM Journal on Computing, V5, P704, DOI 10.1137/0205049

[7]

Grunbaum B, 1967, CONVEX POLYTOPES

[8]

Karp Richard M., 1972, COMPLEXITY COMPUTER, P85

[9] COMPUTER SOLUTIONS OF TRAVELING SALESMAN PROBLEM [J].

LIN, S .

BELL SYSTEM TECHNICAL JOURNAL, 1965, 44 (10) :2245-+

[10] EFFECTIVE HEURISTIC ALGORITHM FOR TRAVELING-SALESMAN PROBLEM [J].

LIN, S ;

KERNIGHAN, BW .