The eternal dominating set problem for interval graphs

Mostrar todas las versiones(2)

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
Descripción
Sumario: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.

Ejemplares similares