کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
6871964 | 684128 | 2016 | 7 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Enumerating minimal dominating sets in chordal bipartite graphs
ترجمه فارسی عنوان
شمارش مجموعه های غالب حاشیه در نمودارهای دو طرفه است
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
حداقل مجموعه غالب، شمارش الگوریتم چند جمله ای خروجی،
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
We show that all minimal dominating sets of a chordal bipartite graph can be generated in incremental polynomial, hence output polynomial, time. Enumeration of minimal dominating sets in graphs is equivalent to enumeration of minimal transversals in hypergraphs. Whether the minimal transversals of a hypergraph can be enumerated in output polynomial time is a well-studied and challenging question that has been open for several decades. With this result we contribute to the known cases having an affirmative reply to this important question.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 199, 30 January 2016, Pages 30-36
Journal: Discrete Applied Mathematics - Volume 199, 30 January 2016, Pages 30-36
نویسندگان
Petr A. Golovach, Pinar Heggernes, Mamadou M. Kanté, Dieter Kratsch, Yngve Villanger,