A linear time algorithm for optimal k-hop dominating set of a tree
We give a linear time algorithm to compute an optimal (minimum) k-hop dominating set D of a tree T  for k?1 k ? 1 . This extends the previous result for an optimal 1-dominating set for trees. We use a rooted form T  of T, with an arbitrary node selected as the root, to direct the search for nodes of D in a bottomup fashion. The decision whether to include a node x in D  or not is based on the subtree of T  at x. Optimal k-hop dominating sets have many important practical applications.
k-hop dominating set graph algorithms rooted tree