کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4648767 | 1342427 | 2008 | 5 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Very large cliques are easy to detect
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله

چکیده انگلیسی
It is known that, for every constant k⩾3k⩾3, the presence of a k-clique (a complete sub-graph on k vertices) in an n -vertex graph cannot be detected by a monotone boolean circuit using much fewer than nknk gates. We show that, for every constant k , the presence of an (n-k)(n-k)-clique in an n -vertex graph can be detected by a monotone circuit using only a logarithmic number of fanin-2 OR gates; the total number of gates does not exceed O(n2logn)O(n2logn). Moreover, if we allow unbounded fanin, then a logarithmic number of gates is enough.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 308, Issue 16, 28 August 2008, Pages 3717–3721
Journal: Discrete Mathematics - Volume 308, Issue 16, 28 August 2008, Pages 3717–3721
نویسندگان
A.E. Andreev, S. Jukna,