A group testing problem for hypergraphs of bounded rank

被引：15

作者：

Triesch, E

机构：

[1] Forsch. Inst. fur Diskrete Math., D-53113 Bonn

来源：

DISCRETE APPLIED MATHEMATICS | 1996年 / 66卷 / 02期

关键词：

group testing; search problems; hypergraphs; Kraft's inequality;

D O I：

10.1016/0166-218X(95)00120-G

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

Suppose that a hypergraph H = (V,E) of rank r is given as well as a probability distribution p(e) (e is an element of E) on the edges. We show that in the usual group testing model the unknown edge can be found by less than - log p(e) + r tests. For the case of the uniform distribution, the result proves a conjecture of Du and Hwang.

引用

页码：185 / 188

页数：4