Distributed algorithms for finding the unique minimum distance dominating set in directed split-stars
A distance-k dominating set D of a directed graph G is a set of vertices such that for every vertex v of G, there is a vertex u?D and the distance between u and v is at most k. Minimum distance-k dominating set is especially important in communication networks for distributed data structures and for server placement. In this paper, we show that there is a unique minimum distance-k dominating set for k=1,2 in a directed split-star, which has recently been developed as a new model of the interconnection network for parallel and distributed computing systems. Moreover, we shall present simple distributed algorithms for finding such sets.
distributed algorithms directed split-stars distance-k dominating set interconnection networks