کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
10151230 | 685009 | 2018 | 14 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Exact algorithms for weak Roman domination
ترجمه فارسی عنوان
الگوریتم های دقیق برای سلطه ضعیف رومی
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
الگوریتم دقیق، الگوریتم نمودار، سلطنت رومی، نمودارهای فاصله،
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
We consider the Weak Roman Domination problem. Given an undirected graph G=(V,E), the aim is to find a weak Roman domination function (wrd-function for short) of minimum cost, i.e. a function f:Vâ{0,1,2} such that every vertex vâV is defended (i.e. there exists a neighbor u of v, possibly u=v, such that f(u)⩾1) and for every vertex vâV with f(v)=0 there exists a neighbor u of v such that f(u)⩾1 and the function fuâv defined by fuâv(v)=1, fuâv(u)=f(u)â1 and fuâv(x)=f(x) otherwise does not contain any undefended vertex. The cost of a wrd-function f is defined by cost(f)=âvâVf(v). The trivial enumeration algorithm runs in time Oâ(3n) and polynomial space and is the best one known for the problem so far. We are breaking the trivial enumeration barrier by providing two faster algorithms: we first prove that the problem can be solved in Oâ(2n) time needing exponential space, and then describe an Oâ(2.2279n) algorithm using polynomial space. Our results rely on structural properties of a wrd-function, as well as on the best polynomial space algorithm for the Red-Blue Dominating Set problem. Moreover we show that the problem can be solved in linear-time on interval graphs.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 248, 30 October 2018, Pages 79-92
Journal: Discrete Applied Mathematics - Volume 248, 30 October 2018, Pages 79-92
نویسندگان
Mathieu Chapelle, Manfred Cochefert, Jean-FraÅcois Couturier, Dieter Kratsch, Romain Letourneur, Mathieu Liedloff, Anthony Perez,