Distributed algorithms for finding the unique minimum distance dominating set in directed split-stars
✍ Scribed by Fu-Hsing Wang; Jou-Ming Chang; Yue-Li Wang; Sun-Jen Huang
- Publisher
- Elsevier Science
- Year
- 2003
- Tongue
- English
- Weight
- 191 KB
- Volume
- 63
- Category
- Article
- ISSN
- 0743-7315
No coin nor oath required. For personal study only.
✦ Synopsis
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 uAD 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.