کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4649596 1342461 2009 11 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Edge search in graphs with restricted test sets
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
Edge search in graphs with restricted test sets
چکیده انگلیسی
We solve this search problem suggested by M. Aigner in [M. Aigner, Combinatorial Search, Teubner, 1988] by deriving lower and sharp upper bounds for cp(G). For the case that G is the complete graph Kn the problem described above is equivalent to the (2,n) group testing problem with test sets of cardinality at most p. We present sharp upper and lower bounds for the worst case number cp of tests for this group testing problem and show that the maximum difference between the upper and the lower bounds is 3.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 309, Issue 20, 28 October 2009, Pages 5932-5942
نویسندگان
,