Artículo

The eternal dominating set problem for interval graphs

Rinemberg, Martín; Soulignac, Francisco JuanIcon
Fecha de publicación: 06/2019
Editorial: Elsevier Science
Revista: Information Processing Letters
ISSN: 0020-0190
Idioma: Inglés
Tipo de recurso: Artículo publicado
Clasificación temática:

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.
Palabras clave: COMBINATORIAL PROBLEMS , ETERNAL DOMINATING SET , INTERVAL GRAPHS , NEOCOLONIZATION
 
Archivos asociados
Tamaño: 120.5Kb
Formato: PDF
.
Licencia
info:eu-repo/semantics/restrictedAccess Excepto donde se diga explícitamente, este item se publica bajo la siguiente descripción: Creative Commons Attribution-NonCommercial-ShareAlike 2.5 Unported (CC BY-NC-SA 2.5)
Identificadores
URI: http://hdl.handle.net/11336/130290
DOI: http://dx.doi.org/10.1016/j.ipl.2019.01.013
URL: https://www.sciencedirect.com/science/article/abs/pii/S0020019019300213
Colecciones
Articulos(SEDE CENTRAL)
Articulos de SEDE CENTRAL
Citación
Rinemberg, Martín; Soulignac, Francisco Juan; The eternal dominating set problem for interval graphs; Elsevier Science; Information Processing Letters; 146; 6-2019; 27-29
Compartir
Altmétricas