کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
6875563 | 1441970 | 2018 | 36 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
On the construction of graphs with a planar bipartite double cover from boolean formulas and its application to counting satisfying solutions
ترجمه فارسی عنوان
در ساخت گراف ها با پوشش دو طرفه دو طرفه از فرمول بولی و کاربرد آن به شمارش راه حل های رضایت بخش
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
نمودار پلانار، دو طرفه دو طرفه، سازگاری کامل دائمی، شمارش راه حل های رضایت بخش،
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
We prove a theorem that describes necessary conditions for the gadgets (i.e., small subgraphs with certain properties) of G to allow a planar bipartite double cover G¨. For arbitrary 3CNF formulas and the known approaches to build G, our theorem shows that gadgets, which enable a planar bipartite double cover, do not exist. However, we show that for certain classes of boolean formulas, e.g., #5Pl-Rtw-2CNF, #7Pl-Rtw-2CNF and #3Forest-3CNF, such gadgets exist, hence these counting problems are in P. The results probably extended to other moduli p and perhaps further counting classes.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 719, 6 April 2018, Pages 21-45
Journal: Theoretical Computer Science - Volume 719, 6 April 2018, Pages 21-45
نویسندگان
Christian Schridde,