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 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
