Artículos de revistas
The Eternal Dominating Set Problem For Proper Interval Graphs
Registro en:
The Eternal Dominating Set Problem For Proper Interval Graphs. Elsevier Science Bv, v. 115, p. 582-587 JUN-AUG-2015.
0020-0190
WOS:000353742700007
10.1016/j.ipl.2015.02.004
Autor
Braga
Andrei; de Souza
Cid C.; Lee
Orlando
Institución
Resumen
Conselho Nacional de Desenvolvimento Científico e Tecnológico (CNPq) 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. (c) 2015 Elsevier B.V. All rights reserved. 115
582 587 Conselho Nacional de Desenvolvimento Científico e Tecnológico (CNPq) Conselho Nacional de Desenvolvimento Científico e Tecnológico (CNPq) CNPq [477692/2012-5, 141964/2013-8, 302804/2010-2, 303947/2008-0]