کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
433853 | 689640 | 2015 | 7 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
A theorem of Ore and self-stabilizing algorithms for disjoint minimal dominating sets
ترجمه فارسی عنوان
یک قضیه سنگ معدن و الگوریتم های خود پاکسازی برای مجموعه های غالب مانع نشده
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
نمودار، الگوریتم خود تثبیت کننده، حداقل مجموعه غالب، مجموعه مستقل حداکثر
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
A theorem of Ore [20] states that if D is a minimal dominating set in a graph G=(V,E)G=(V,E) having no isolated nodes, then V−DV−D is a dominating set. It follows that such graphs must have two disjoint minimal dominating sets R and B. We describe a self-stabilizing algorithm for finding such a pair of sets. It also follows from Ore's theorem that in a graph with no isolates, one can find disjoint sets R and B where R is maximal independent and B is minimal dominating. We describe a self-stabilizing algorithm for finding such a pair. Both algorithms are described using the Distance-2 model, but can be converted to the usual Distance-1 model [7], yielding running times of O(n2m)O(n2m).
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 593, 16 August 2015, Pages 132–138
Journal: Theoretical Computer Science - Volume 593, 16 August 2015, Pages 132–138
نویسندگان
Stephen T. Hedetniemi, David P. Jacobs, K.E. Kennedy,