ON 2 GEOMETRIC PROBLEMS RELATED TO THE TRAVELING SALESMAN PROBLEM

被引：90

作者：

PAPADIMITRIOU, CH ^{[1
]}

VAZIRANI, UV ^{[1
]}

机构：

[1] UNIV CALIF BERKELEY,DEPT COMP SCI,BERKELEY,CA 94720

来源：

关键词：

D O I：

10.1016/0196-6774(84)90029-4

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

引用

页码：231 / 246

页数：16

共 12 条

[1] Christofides N., 2022, OPERATIONS RES FORUM, V3, DOI [10.1007/s43069-021-00101-z, DOI 10.1007/S43069-021-00101-Z]
[2] Garey Michael R., 1979, COMPUTERS INTRACTABI
[3] GAREY MR, 1976, 8TH P ANN ACM S THEO, P10
[4] ITAI A, 1982, SIAM J COMPUT
[5] JOHNSON DS, 1982, TRAVELLING SALESMAN, pCH3
[6] Karp R.M., 1972, COMPLEXITY COMPUTER
[7] LAWLER EW, 1982, TRAVELLING SALESMAN
[8] Papadimitriou C. H., 1977, Theoretical Computer Science, V4, P237, DOI 10.1016/0304-3975(77)90012-3
[9] PAPADIMITRIOU CH, 1976, 8TH P ANN ACM S THEO, P1
[10] NP-COMPLETENESS OF THE HAMILTONIAN CYCLE PROBLEM IN PLANAR DIGRAPHS WITH DEGREE BOUND 2
PLESNIK, J
[J]. INFORMATION PROCESSING LETTERS, 1979, 8 (04) : 199 - 201