The eternal dominating set problem for interval graphs
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.
Guardado en:
| Autor principal: | |
|---|---|
| Otros Autores: | |
| Formato: | Capítulo de libro |
| Lenguaje: | Inglés |
| Publicado: |
Elsevier B.V.
2019
|
| Acceso en línea: | Registro en Scopus DOI Handle Registro en la Biblioteca Digital |
| Aporte de: | Registro referencial: Solicitar el recurso aquí |
| LEADER | 03883caa a22005777a 4500 | ||
|---|---|---|---|
| 001 | PAPER-25565 | ||
| 003 | AR-BaUEN | ||
| 005 | 20240927190134.0 | ||
| 008 | 190410s2019 xx ||||fo|||| 00| 0 eng|d | ||
| 024 | 7 | |2 scopus |a 2-s2.0-85061456843 | |
| 030 | |a IFPLA | ||
| 040 | |a Scopus |b spa |c AR-BaUEN |d AR-BaUEN | ||
| 100 | 1 | |a Rinemberg, M. | |
| 245 | 1 | 4 | |a The eternal dominating set problem for interval graphs |
| 260 | |b Elsevier B.V. |c 2019 | ||
| 270 | 1 | 0 | |m Soulignac, F.J.; CONICET, Departamento de Ciencia y Tecnología, Universidad Nacional de QuilmesArgentina; email: francisco.soulignac@unq.edu.ar |
| 504 | |a 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 | ||
| 504 | |a 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 | ||
| 504 | |a 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 | ||
| 504 | |a 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 | ||
| 504 | |a Goddard, W., Hedetniemi, S.M., Hedetniemi, S.T., Eternal security in graphs (2005) J. Comb. Math. Comb. Comput., 52, pp. 169-180 | ||
| 504 | |a Klostermeyer, W.F., MacGillivray, G., Eternal dominating sets in graphs (2009) J. Comb. Math. Comb. Comput., 68, pp. 97-111 | ||
| 504 | |a Klostermeyer, W.F., Mynhardt, C.M., Protecting a graph with mobile guards (2016) Appl. Anal. Discrete Math., 10 (1), pp. 1-29 | ||
| 506 | |2 openaire |e Política editorial | ||
| 520 | 3 | |a 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. |l eng | |
| 536 | |a Detalles de la financiación: 2015-2419 | ||
| 536 | |a Detalles de la financiación: We thank the anonymous reviewers for their helpful comments that helped to improve the presentation of this article. The second author was supported by PICT ANPCyT Grant 2015-2419 . | ||
| 593 | |a Departamento de Computación, Universidad de Buenos Aires, Argentina | ||
| 593 | |a CONICET, Departamento de Ciencia y Tecnología, Universidad Nacional de Quilmes, Argentina | ||
| 690 | 1 | 0 | |a COMBINATORIAL PROBLEMS |
| 690 | 1 | 0 | |a ETERNAL DOMINATING SET |
| 690 | 1 | 0 | |a INTERVAL GRAPHS |
| 690 | 1 | 0 | |a NEOCOLONIZATION |
| 690 | 1 | 0 | |a COMPUTER APPLICATIONS |
| 690 | 1 | 0 | |a DATA PROCESSING |
| 690 | 1 | 0 | |a COMBINATORIAL PROBLEM |
| 690 | 1 | 0 | |a CONNECTED COVER |
| 690 | 1 | 0 | |a ETERNAL DOMINATING SETS |
| 690 | 1 | 0 | |a INTERVAL GRAPH |
| 690 | 1 | 0 | |a LINEAR ALGORITHMS |
| 690 | 1 | 0 | |a NEOCOLONIZATION |
| 690 | 1 | 0 | |a GRAPHIC METHODS |
| 700 | 1 | |a Soulignac, F.J. | |
| 773 | 0 | |d Elsevier B.V., 2019 |g v. 146 |h pp. 27-29 |p Inf. Process. Lett. |x 00200190 |w (AR-BaUEN)CENRE-1599 |t Information Processing Letters | |
| 856 | 4 | 1 | |u https://www.scopus.com/inward/record.uri?eid=2-s2.0-85061456843&doi=10.1016%2fj.ipl.2019.01.013&partnerID=40&md5=5acfe69fdc61a553f83af9c1e1fb9719 |y Registro en Scopus |
| 856 | 4 | 0 | |u https://doi.org/10.1016/j.ipl.2019.01.013 |y DOI |
| 856 | 4 | 0 | |u https://hdl.handle.net/20.500.12110/paper_00200190_v146_n_p27_Rinemberg |y Handle |
| 856 | 4 | 0 | |u https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_00200190_v146_n_p27_Rinemberg |y Registro en la Biblioteca Digital |
| 961 | |a paper_00200190_v146_n_p27_Rinemberg |b paper |c PE | ||
| 962 | |a info:eu-repo/semantics/article |a info:ar-repo/semantics/artículo |b info:eu-repo/semantics/publishedVersion | ||
| 999 | |c 86518 | ||