K-Dominating Sets: A Synchronous Distributed Algorithm

Title: k-Dominating Sets: A Synchronous Distributed Algorithm

Abstract: This research focuses on finding k-dominating sets in a connected undirected graph G with n nodes and m edges. The algorithm aims to minimize the set's size, which is known to be at most ⌊n/(k+ 1)⌋. The research proposes a new synchronous distributed algorithm that improves on the previously known algorithm's message complexity and is conceptually simpler.

Main Research Question: Can we develop a more efficient algorithm for finding k-dominating sets in a connected undirected graph, while maintaining the same time complexity?

Methodology: The study uses the standard synchronous distributed model, where nodes function in lockstep and communicate through bidirectional channels. The algorithm consists of two stages: partitioning the graph into a rooted spanning forest F and then approaching each tree U as described earlier. The algorithm outputs a k-dominating set D, which is a union of sets from each tree.

Results: The new algorithm improves on the previously known algorithm's message complexity, reducing it to O(mlogk+nlogklog∗n). It maintains the same time complexity of O(klog∗n).

Implications: The new algorithm is more efficient in terms of communication needs, making it a better choice for real-world applications. It also simplifies the algorithm's structure, making it easier to understand and implement.

Conclusion: The research successfully developed a new synchronous distributed algorithm for finding k-dominating sets in a connected undirected graph. The algorithm improves on the previously known algorithm's message complexity and is conceptually simpler. Future research could focus on applying the algorithm to real-world scenarios and exploring its potential in other graph theory problems.

Link to Article: https://arxiv.org/abs/0309040v1 Authors: arXiv ID: 0309040v1