Nonadaptive algorithms for threshold group testing

Hong Bin Chen*, Hung-Lin Fu

*Corresponding author for this work

Research output: Contribution to journalArticle

27 Scopus citations

Abstract

Threshold group testing first proposed by Damaschke is a generalization of classic group testing. Specifically, a group test is positive (negative) if it contains at least u (at most l) positives, and if the number of positives is between l and u, the test outcome is arbitrary. Although sequential group testing algorithms have been proposed, it is unknown whether an efficient nonadaptive algorithm exists. In this paper, we give an affirmative answer to this problem by providing efficient nonadaptive algorithms for the threshold model. The key observation is that disjunct matrices, a standard tool for group testing designs, also work in this threshold model. This paper improves and extends previous results in three ways:. 1. The algorithms we propose work in one stage, which saves time for testing. 2. The test complexity is lower than previous results, at least for the number of elements which need to be tested is sufficiently large. 3. A limited number of erroneous test outcomes are allowed.

Original languageEnglish
Pages (from-to)1581-1585
Number of pages5
JournalDiscrete Applied Mathematics
Volume157
Issue number7
DOIs
StatePublished - 6 Apr 2009

Keywords

  • Graph search
  • Nonadaptive algorithms
  • Threshold group testing

Fingerprint Dive into the research topics of 'Nonadaptive algorithms for threshold group testing'. Together they form a unique fingerprint.

  • Cite this