2018/12/03 by Soulignac, Francisco J.
#68R10 #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics
paper · doi:10.48550/arxiv.1812.00689
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. (Improved Algorithms for k-Domination and Total k-Domination in Proper Interval Graphs, Lecture Notes in Comput. Sci. 10856, 290--302, 2018) 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.