Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
10331049 | Information Processing Letters | 2016 | 10 Pages |
Abstract
We give a linear time algorithm to compute an optimal (minimum) k-hop dominating set D of a tree T for 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 bottom-up 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.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Sukhamay Kundu, Subhashis Majumder,