Artículo

Rinemberg, M.; Soulignac, F.J."The eternal dominating set problem for interval graphs" (2019) Information Processing Letters. 146:27-29
Estamos trabajando para incorporar este artículo al repositorio
Consulte el artículo en la página del editor
Consulte la política de Acceso Abierto del editor

Abstract:

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.

Registro:

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

Referencias:

  • Booth, K.S., Lueker, G.S., Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms (1976) J. Comput. Syst. Sci., 13 (3), pp. 335-379
  • Braga, A., de Souza, C.C., Lee, O., The eternal dominating set problem for proper interval graphs (2015) Inf. Process. Lett., 115 (6-8), pp. 582-587
  • Burger, A.P., Cockayne, E.J., Gründlingh, W.R., Mynhardt, C.M., van Vuuren, J.H., Winterbach, W., Infinite order domination in graphs (2004) J. Comb. Math. Comb. Comput., 50, pp. 179-194
  • Finbow, S., Gaspers, S., Messinger, M.-E., Ottaway, P., A note on the eternal dominating set problem (2018) Int. J. Game Theory, 47 (2), pp. 543-555
  • Goddard, W., Hedetniemi, S.M., Hedetniemi, S.T., Eternal security in graphs (2005) J. Comb. Math. Comb. Comput., 52, pp. 169-180
  • Klostermeyer, W.F., MacGillivray, G., Eternal dominating sets in graphs (2009) J. Comb. Math. Comb. Comput., 68, pp. 97-111
  • Klostermeyer, W.F., Mynhardt, C.M., Protecting a graph with mobile guards (2016) Appl. Anal. Discrete Math., 10 (1), pp. 1-29

Citas:

---------- APA ----------
Rinemberg, M. & Soulignac, F.J. (2019) . The eternal dominating set problem for interval graphs. Information Processing Letters, 146, 27-29.
http://dx.doi.org/10.1016/j.ipl.2019.01.013
---------- CHICAGO ----------
Rinemberg, M., Soulignac, F.J. "The eternal dominating set problem for interval graphs" . Information Processing Letters 146 (2019) : 27-29.
http://dx.doi.org/10.1016/j.ipl.2019.01.013
---------- MLA ----------
Rinemberg, M., Soulignac, F.J. "The eternal dominating set problem for interval graphs" . Information Processing Letters, vol. 146, 2019, pp. 27-29.
http://dx.doi.org/10.1016/j.ipl.2019.01.013
---------- VANCOUVER ----------
Rinemberg, M., Soulignac, F.J. The eternal dominating set problem for interval graphs. Inf. Process. Lett. 2019;146:27-29.
http://dx.doi.org/10.1016/j.ipl.2019.01.013