CPL - Chalmers Publication Library
| Utbildning | Forskning | Styrkeområden | Om Chalmers | In English In English Ej inloggad.

A toolbox for provably optimal multistage strict group testing strategies

Peter Damaschke (Institutionen för data- och informationsteknik, Datavetenskap, Algoritmer (Chalmers) ; Institutionen för data- och informationsteknik, Datavetenskap, Bioinformatik (Chalmers)) ; Azam Sheikh Muhammad (Institutionen för data- och informationsteknik, Datavetenskap, Algoritmer (Chalmers))
19th International Computing and Combinatorics Conference COCOON 2013, Lecture Notes in Computer Science Vol. 7936 (2013), p. 446-457.
[Konferensbidrag, refereegranskat]

Group testing is the problem of identifying up to d defectives in a set 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 no more than d defectives are present. We develop combinatorial tools that are powerful enough to compute many exact t(n,d,s) values. This extends the work of Huang and Hwang (2001) for s=1 to multistage strategies. The latter are interesting since it is known that asymptotically nearly optimal group testing is possible already in s=2 stages. Besides other tools we generalize d-disjunct matrices to any candidate hypergraphs, which enables us to express optimal test numbers for s=2 as chromatic numbers of certain conflict graphs. As a proof of concept we determine almost all test numbers for n up to 10, and t(n,2,2) for some larger n.

Nyckelord: group testing, disjunct matrix, chromatic number, nonadaptive, lower bounds



Den här publikationen ingår i följande styrkeområden:

Läs mer om Chalmers styrkeområden  

Denna post skapades 2013-06-18. Senast ändrad 2015-02-11.
CPL Pubid: 178823