pith. sign in

arxiv: 1812.00689 · v1 · pith:HHKTFU4Xnew · submitted 2018-12-03 · 💻 cs.DM · math.CO

Total 2-domination of proper interval graphs

classification 💻 cs.DM math.CO
keywords totaldominationintervalproperdominatinggraphgraphstime
0
0 comments X
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.