INVESTIGADORES
SOULIGNAC Francisco Juan
artículos
Título:
Total 2-domination of proper interval graphs
Autor/es:
SOULIGNAC, FRANCISCO J.
Revista:
DISCRETE APPLIED MATHEMATICS
Editorial:
ELSEVIER SCIENCE BV
Referencias:
Año: 2021 vol. 302 p. 256 - 262
ISSN:
0166-218X
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.
