A Distributed Algorithm for Minimum Distance-k Domination in Trees
Vol. 19, no. 1, pp. 223-242, 2015. Regular paper.
Abstract While efficient algorithms for finding minimal distance-k dominating sets exist, finding minimum such sets is NP-hard even for bipartite graphs. This paper presents a distributed algorithm to determine a minimum (connected) distance-k dominating set and a maximum distance-2k independent set of a tree T. It terminates in O(height(T)) rounds and uses O(logk) space. To the best of our knowledge this is the first distributed algorithm that computes a minimum (as opposed to a minimal) distance-k dominating set for trees. The algorithm can also be applied to general graphs, albeit the distance-k dominating sets are not necessarily minimal.
Submitted: January 2014.
Reviewed: June 2014.
Revised: July 2014.
Reviewed: November 2014.
Revised: December 2014.
Accepted: March 2015.
Final: March 2015.
Published: March 2015.
Communicated by Sue Whitesides
article (PDF)