کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
6874185 | 1441027 | 2018 | 6 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Cliques enumeration and tree-like resolution proofs
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
We show the close connection between the enumeration of cliques in a k-clique free graph G, the running time of DPLL-style algorithms for k-clique problem, and the length of tree-like resolution refutations for formula Clique(G,k), which claims that G has a k-clique. The length of any such tree-like refutation is within a “fixed parameter tractable” factor from the number of cliques in the graph. We then proceed to drastically simplify the proofs of the lower bounds for the length of tree-like resolution refutations of Clique(G,k) shown in Beyersdorff et at. 2013, Lauria et al. 2017, which now reduce to a simple estimate of said quantity.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Information Processing Letters - Volume 135, July 2018, Pages 62-67
Journal: Information Processing Letters - Volume 135, July 2018, Pages 62-67
نویسندگان
Massimo Lauria,