RELATIVE COMPLEXITY OF EVALUATING THE OPTIMUM COST AND CONSTRUCTING THE OPTIMUM FOR MAXIMIZATION PROBLEMS

被引：7

作者：

CRESCENZI, P

SILVESTRI, R

机构：

[1] Dipartimento di Matematika, Università di Roma La Sapienza. Piazzale Aldo Moro 2

来源：

关键词：

many-one reducibility; NP-complete problem; Optimization problem; Turing reducibility;

D O I：

10.1016/0020-0190(90)90188-4

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

[No abstract available]

引用

页码：221 / 226

页数：6

共 8 条

[1]

ALLENDER EW, 1986, LECT NOTES COMPUT SC, V223, P1

[2]

AUSIELLO G, 1980, CALCOLO, V16, P539

[3]

CRESCENZI P, 1988, 26TH P ANN ALL C COM

[4]

GASARCH W, 1986, 1652 U MAR DEP COMP

[5]

KRENTEL MW, 1986, 18TH P ANN ACM S THE, P69

LONG, TJ .

[7]

SCHONING U, 1985, LECTURE NOTES COMPUT, V211

[8]

Valiant L. G., 1976, Information Processing Letters, V5, P20, DOI 10.1016/0020-0190(76)90097-1