کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4655334 | 1632946 | 2014 | 22 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Strict group testing and the set basis problem
ترجمه فارسی عنوان
تست گروه شدید و مشکل اساسی مجموعه
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
ریاضیات گسسته و ترکیبات
چکیده انگلیسی
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.44log2n+o(log2n).
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Combinatorial Theory, Series A - Volume 126, August 2014, Pages 70-91
Journal: Journal of Combinatorial Theory, Series A - Volume 126, August 2014, Pages 70-91
نویسندگان
Peter Damaschke, Azam Sheikh Muhammad, Gábor Wiener,