The eternal dominating set problem for interval graphs

Rinemberg, Martín; Soulignac, Francisco Juan

info:eu-repo/semantics/article

Fecha

2019-06

Registro en:

Rinemberg, Martín; Soulignac, Francisco Juan; The eternal dominating set problem for interval graphs; Elsevier Science; Information Processing Letters; 146; 6-2019; 27-29

0020-0190

http://hdl.handle.net/11336/130290

CONICET Digital

CONICET

https://repositorioslatinoamericanos.uchile.cl/handle/2250/4338366

Autor

Rinemberg, Martín

Soulignac, Francisco Juan

Institución

Consejo Nacional de Investigaciones Científicas y Tecnológicas (Argentina)

Resumen

We prove that, in games in which all the guards move at the same turn, the eternal domination and the clique-connected cover numbers coincide for interval graphs. A linear algorithm for the eternal dominating set problem on interval graphs is obtained as a by-product.

Materias

COMBINATORIAL PROBLEMS

ETERNAL DOMINATING SET

INTERVAL GRAPHS

NEOCOLONIZATION

Mostrar el registro completo del ítem