کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
6874258 | 686948 | 2015 | 6 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
The Eternal Dominating Set problem for proper interval graphs
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
![عکس صفحه اول مقاله: The Eternal Dominating Set problem for proper interval graphs The Eternal Dominating Set problem for proper interval graphs](/preview/png/6874258.png)
چکیده انگلیسی
In this paper, we solve the Eternal Dominating Set problem for proper interval graphs. We prove that, in this case, the optimal value of the problem equals the largest size of an independent set. As a consequence, we show that the problem can be solved in linear time for such graphs. To obtain the result, we first consider another problem in which a vertex can be occupied by an arbitrary number of guards. We then derive a lower bound on the optimal value of this latter problem, and prove that, for proper interval graphs, it is the same as the optimum of the first problem.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Information Processing Letters - Volume 115, Issues 6â8, JuneâAugust 2015, Pages 582-587
Journal: Information Processing Letters - Volume 115, Issues 6â8, JuneâAugust 2015, Pages 582-587
نویسندگان
Andrei Braga, Cid C. de Souza, Orlando Lee,