Artículo

Total 2-domination of proper interval graphs

Soulignac, Francisco JuanIcon
Fecha de publicación: 10/2021
Editorial: Elsevier Science
Revista: Discrete Applied Mathematics
ISSN: 0166-218X
Idioma: Inglés
Tipo de recurso: Artículo publicado
Clasificación temática:

Resumen

A set of vertices W of a graph G is a total k-dominating set when every vertex of G has at least k neighbors in W. In a recent article, Chiarelli et al. (2019) prove that a total k-dominating set can be computed in O(n3k) time when G is a proper interval graph with n vertices and m edges. In this note we reduce the time complexity to O(m) for k=2.
Palabras clave: PROPER INTERVAL GRAPHS , STRAIGHT ORIENTED GRAPHS , TOTAL 2-DOMINATION
 
Archivos asociados
Thumbnail
 
Tamaño: 200.5Kb
Formato: PDF
.
Licencia
info:eu-repo/semantics/openAccess Excepto donde se diga explícitamente, este item se publica bajo la siguiente descripción: Creative Commons Attribution-NonCommercial-ShareAlike 2.5 Unported (CC BY-NC-SA 2.5)
Identificadores
URI: http://hdl.handle.net/11336/173291
DOI: http://dx.doi.org/10.1016/j.dam.2021.07.015
URL: https://arxiv.org/abs/1812.00689?context=math.CO#:~:text=A%20set%20of%20vertices
Colecciones
Articulos(ICC)
Articulos de INSTITUTO DE INVESTIGACION EN CIENCIAS DE LA COMPUTACION
Citación
Soulignac, Francisco Juan; Total 2-domination of proper interval graphs; Elsevier Science; Discrete Applied Mathematics; 302; 10-2021; 256-262
Compartir
Altmétricas