ON THE COMPLEXITY OF UNIQUE SOLUTIONS

被引：50

作者：

PAPADIMITRIOU, CH ^{[1
]}

机构：

[1] NATL TECH UNIV ATHENS,GR-147 ATHENS,GREECE

来源：

JOURNAL OF THE ACM | 1984年 / 31卷 / 02期

关键词：

OPERATIONS RESEARCH;

D O I：

10.1145/62.322435

中图分类号：

TP3 [计算技术、计算机技术];

学科分类号：

0812 ;

摘要：

We show that the problem of deciding whether an instance of the traveling salesman problem has a uniquely optimal solution is complete for DELTA //2**p.

引用

页码：392 / 400

页数：9

共 13 条

[1]

[Anonymous], 1971, STOC 71, DOI DOI 10.1145/800157.805047

[2]

FRAENKEL A, 1978, 19TH P ANN S F COMP, P55

[3]

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

[4]

Garey Michael R., 1979, COMPUTERS INTRACTABI

[5]

ITAI A, 1981, SIAM J COMPUT, V10

[6]

Karp R.M., 1972, COMPLEXITY COMPUTER

[7]

Lichtenstein D., 1978, 19th Annual Symposium on Foundations of Computer Science, P48, DOI 10.1109/SFCS.1978.17

[8] FLOWSHOP SCHEDULING WITH LIMITED TEMPORARY-STORAGE [J].

PAPADIMITRIOU, CH ;

KANELLAKIS, PC .

JOURNAL OF THE ACM, 1980, 27 (03) :533-549

[9] ADJACENCY RELATION ON TRAVELING SALESMAN POLYTOPE IS NP-COMPLETE [J].

PAPADIMITRIOU, CH .

MATHEMATICAL PROGRAMMING, 1978, 14 (03) :312-324

[10]

Papadimitriou CH., 1982, COMBINATORIAL OPTIMI

← 1 2 →