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:
Detalles Bibliográficos
Autores principales: Rinemberg, M., Soulignac, F.J.
Formato: JOUR
Materias:
Combinatorial problems
Eternal dominating set
Interval graphs
Neocolonization
Computer applications
Data processing
Combinatorial problem
Connected cover
Eternal dominating sets
Interval graph
Linear algorithms
Graphic methods
Acceso en línea:http://hdl.handle.net/20.500.12110/paper_00200190_v146_n_p27_Rinemberg
Aporte de:
Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA) de Universidad de Buenos Aires
id todo:paper_00200190_v146_n_p27_Rinemberg
record_format dspace
spelling todo:paper_00200190_v146_n_p27_Rinemberg2023-10-03T14:16:41Z The eternal dominating set problem for interval graphs Rinemberg, M. Soulignac, F.J. 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 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. JOUR info:eu-repo/semantics/openAccess http://creativecommons.org/licenses/by/2.5/ar http://hdl.handle.net/20.500.12110/paper_00200190_v146_n_p27_Rinemberg
institution Universidad de Buenos Aires
institution_str I-28
repository_str R-134
collection Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA)
topic 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
spellingShingle 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
Rinemberg, M.
Soulignac, F.J.
The eternal dominating set problem for interval graphs
topic_facet 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
description 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.
format JOUR
author Rinemberg, M.
Soulignac, F.J.
author_facet Rinemberg, M.
Soulignac, F.J.
author_sort Rinemberg, M.
title The eternal dominating set problem for interval graphs
title_short The eternal dominating set problem for interval graphs
title_full The eternal dominating set problem for interval graphs
title_fullStr The eternal dominating set problem for interval graphs
title_full_unstemmed The eternal dominating set problem for interval graphs
title_sort eternal dominating set problem for interval graphs
url http://hdl.handle.net/20.500.12110/paper_00200190_v146_n_p27_Rinemberg
work_keys_str_mv AT rinembergm theeternaldominatingsetproblemforintervalgraphs
AT soulignacfj theeternaldominatingsetproblemforintervalgraphs
AT rinembergm eternaldominatingsetproblemforintervalgraphs
AT soulignacfj eternaldominatingsetproblemforintervalgraphs
_version_ 1782026489485590528

Ejemplares similares