ICS Theory Group

ICS 269, Fall 2004: Theory Seminar

15 Oct 2004:
Very Efficient Non-Adaptive Group Testing
David Eppstein, Michael T. Goodrich, and Daniel S. Hirschberg

In combinatorial group testing, a set of items is given, most of which are good (or pure) and some of which might be defective (or contaminated). Tests for contamination can be applied to arbitrary subsets of these items.

We present descriptions of very efficient non-adaptive combinatorial group testing algorithms that determine which d items out of a given set of n items are defective for particular small values of d. These algorithms require fewer computational resources and/or fewer combinatorial tests than previously known algorithms for all practical values of n.