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. © 2019 Elsevier B.V.
Documento: | Artículo |
Título: | The eternal dominating set problem for interval graphs |
Autor: | Rinemberg, M.; Soulignac, F.J. |
Filiación: | Departamento de Computación, Universidad de Buenos Aires, Argentina CONICET, Departamento de Ciencia y Tecnología, Universidad Nacional de Quilmes, Argentina |
Palabras clave: | Combinatorial problems; Eternal dominating set; Interval graphs; Neocolonization; Computer applications; Data processing; Combinatorial problem; Connected cover; Eternal dominating sets; Interval graph; Linear algorithms; Neocolonization; Graphic methods |
Año: | 2019 |
Volumen: | 146 |
Página de inicio: | 27 |
Página de fin: | 29 |
DOI: | http://dx.doi.org/10.1016/j.ipl.2019.01.013 |
Handle: | http://hdl.handle.net/20.500.12110/paper_00200190_v146_n_p27_Rinemberg |
Título revista: | Information Processing Letters |
Título revista abreviado: | Inf. Process. Lett. |
ISSN: | 00200190 |
CODEN: | IFPLA |
Registro: | https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_00200190_v146_n_p27_Rinemberg |