Total 2-domination of proper interval graphs
classification
💻 cs.DM
math.CO
keywords
totaldominationintervalproperdominatinggraphgraphstime
read the original abstract
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(n^{3k})$ 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$.
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.