کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
8903151 1632403 2018 8 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Identifying defective sets using queries of small size
ترجمه فارسی عنوان
شناسایی مجموعه های معیوب با استفاده از پرس و جو از اندازه های کوچک
کلمات کلیدی
تست گروه، جستجوی ترکیبی تفکیکپذیری جداگانه، هیپرگراسیون رایگان اتحادیه،
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
چکیده انگلیسی
We examine the following version of a classic combinatorial search problem introduced by Rényi: Given a finite set X of n elements we want to identify an unknown subset Y of X, which is known to have exactly d elements, by means of testing, for as few as possible subsets A of X, whether A intersects Y or not. We are primarily concerned with the non-adaptive model, where the family of test sets is specified in advance, in the case where each test set is of size at most some given natural number k. Our main results are nearly tight bounds on the minimum number of tests necessary when d and k are fixed and n is large enough.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 341, Issue 1, January 2018, Pages 143-150
نویسندگان
, , , ,