Name
Abstract | ||
|---|---|---|
Group testing is the problem to identify up to d defectives out of n elements, by testing subsets for the presence of defectives. Let t(n,d,s) be the optimal number of tests needed by an s-stage strategy in the strict group testing model where the searcher must also verify that at most d defectives are present. We start building a combinatorial theory of strict group testing. We compute many exact t(n,d,s) values, thereby extending known results for s=1 to multistage strategies. These are interesting since asymptotically nearly optimal group testing is possible already in s=2 stages. Besides other combinatorial tools we generalize d-disjunct matrices to any candidate hypergraphs, and we reveal connections to the set basis problem and communication complexity. As a proof of concept we apply our tools to determine almost all test numbers for n≤10 and some further t(n,2,2) values. We also show t(n,2,2)≤2.44log2n+o(log2n). |
Year | DOI | Venue |
|---|---|---|
2014 | 10.1016/j.jcta.2014.04.005 | Journal of Combinatorial Theory, Series A |
Keywords | Field | DocType |
Group testing,Hypergraph,Set basis,Graph coloring,d-Disjunct matrix | Discrete mathematics,Binary logarithm,Combinatorics,Matrix (mathematics),Hypergraph,Constraint graph,Communication complexity,Proof of concept,Group testing,Mathematics,Graph coloring | Journal |
Volume | ISSN | Citations |
126 | 0097-3165 | 2 |
PageRank | References | Authors |
0.37 | 21 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Peter Damaschke | 1 | 471 | 56.99 |
| Azam Sheikh Muhammad | 2 | 34 | 4.45 |
| Gábor Wiener | 3 | 64 | 10.65 |