کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
6871132 | 1440179 | 2018 | 11 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Domination problems with no conflicts
ترجمه فارسی عنوان
مشکلات سلطه بدون درگیری
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
In recent works, authors added conflicts to classical discrete optimization problems. In this paper, a conflict is a pair of vertices that cannot be both in a solution. Set of conflicts can be viewed as edges of a so called conflict graph. An instance is then a support graph and a conflict graph. With these new constraints, the existence of a solution (dominating set or independent dominating set) with no conflicts is no more guaranteed. We explore this subject and we prove that it is NP-complete to decide the existence of a solution even in very restricted classes of graphs and conflicts (sparse or dense). We also propose polynomial algorithms for some sub-cases, using deterministic finite automata.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 244, 31 July 2018, Pages 78-88
Journal: Discrete Applied Mathematics - Volume 244, 31 July 2018, Pages 78-88
نویسندگان
Alexis Cornet, Christian Laforest,