کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4951158 | 1441195 | 2017 | 19 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Fixed points in conjunctive networks and maximal independent sets in graph contractions
ترجمه فارسی عنوان
نقاط ثابت در شبکه های همگرا و مجموعه های حداکثر مستقل در انقباض های گراف
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
شبکه بولی، نقطه ثابت، مجموعه مستقل حداکثر، انقباض لبه،
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
Given a graph G, viewed as a loop-less symmetric digraph, we study the maximum number of fixed points in a conjunctive boolean network with G as interaction graph. We prove that if G has no induced C4, then this quantity equals both the number of maximal independent sets in G and the maximum number of maximal independent sets among all the graphs obtained from G by contracting some edges. We also prove that, in the general case, it is coNP-hard to decide if one of these equalities holds, even if G has a unique induced C4.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Computer and System Sciences - Volume 88, September 2017, Pages 145-163
Journal: Journal of Computer and System Sciences - Volume 88, September 2017, Pages 145-163
نویسندگان
Julio Aracena, Adrien Richard, Lilian Salinas,