Nonadaptive algorithms for threshold group testing

檔案

日期

2009-04-06

類型

期刊名稱

DISCRETE APPLIED MATHEMATICS

卷期與頁次

第 157 卷第 7 期,頁 1581–1585

ISSN

0166-218X

語言

英文

摘要

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 1) positives, and if the number of positives is between I 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. (C) 2008 Elsevier B.V. All rights reserved.

所屬典藏

期刊論文
顯示完整詮釋資料 統計資料

引用此條目

Chen, H.-B., & Fu, H.-L. (2009). Nonadaptive algorithms for threshold group testing. DISCRETE APPLIED MATHEMATICS, 157(7), 1581–1585. https://doi.org/10.1016/j.dam.2008.06.003

BibTeX RIS

引用文字依 APA 第 7 版格式自動產生,使用前請再核對。

分享

永久網址:https://ir.lib.nycu.edu.tw/handle/11536/7380