THE COMPLEXITY OF DETERMINACY PROBLEM ON GROUP-TESTING

被引：0

作者：

YANG, F ^{[1
]}

DU, DZ ^{[1
]}

机构：

[1] CHINESE ACAD SCI,INST APPL MATH,BEIJING,PEOPLES R CHINA

来源：

DISCRETE APPLIED MATHEMATICS | 1990年 / 28卷 / 01期

关键词：

Group testing; NP-completeness; polynomial-time algorithm;

D O I：

10.1016/0166-218X(90)90095-T

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

The complexity of group testing is a long-standing open problem. Recently, Du and Ko studied some related problems which can explain the hardness of group testing undirectly. One of such problems is called the determinacy problem on which they left open questions for some models. In this paper, we answer all of them. © 1990.

引用

页码：71 / 81

页数：11

共 5 条

[1] DORFMAN R, 1943, ANN MATH STAT, V14, P4436
[2] SOME COMPLETENESS RESULTS ON DECISION TREES AND GROUP-TESTING
DU, DZ
KO, KI
[J]. SIAM JOURNAL ON ALGEBRAIC AND DISCRETE METHODS, 1987, 8 (04): : 762 - 777
[3] HYPERGEOMETRIC AND GENERALIZED HYPERGEOMETRIC GROUP-TESTING
HWANG, FK
SONG, TT
DU, DZ
[J]. SIAM JOURNAL ON ALGEBRAIC AND DISCRETE METHODS, 1981, 2 (04): : 426 - 428
[4] Papadimitriou C. H., 1998, COMBINATORIAL OPTIMI
[5] Valiant L. G., 1979, Theoretical Computer Science, V8, P189, DOI 10.1016/0304-3975(79)90044-6

← 1 →