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

Strict group testing and the set basis problem

Peter Damaschke (Institutionen för data- och informationsteknik, Datavetenskap, Algoritmer (Chalmers)) ; Azam Sheikh Muhammad (Institutionen för data- och informationsteknik, Datavetenskap, Algoritmer (Chalmers)) ; Gabor Wiener
Journal of combinatorial theory. Series A (0097-3165). Vol. 126 (2014), p. 70-91.
[Artikel, refereegranskad vetenskaplig]

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.44*log n+o(log n).

Nyckelord: group testing, hypergraph, set basis, graph coloring, d-disjunct matrix



Denna post skapades 2014-05-28. Senast ändrad 2015-02-11.
CPL Pubid: 198643

 

Läs direkt!


Länk till annan sajt (kan kräva inloggning)


Institutioner (Chalmers)

Institutionen för data- och informationsteknik, Datavetenskap, Algoritmer (Chalmers)

Ämnesområden

Diskret matematik

Chalmers infrastruktur