Near-Optimal Distributed Approximation of Minimum-Weight Connected Dominating Set

Preprint English OPEN
Ghaffari, Mohsen;
  • Subject: Computer Science - Distributed, Parallel, and Cluster Computing | Computer Science - Data Structures and Algorithms
    acm: MathematicsofComputing_DISCRETEMATHEMATICS

This paper presents a near-optimal distributed approximation algorithm for the minimum-weight connected dominating set (MCDS) problem. The presented algorithm finds an $O(\log n)$ approximation in $\tilde{O}(D+\sqrt{n})$ rounds, where $D$ is the network diameter and $n$... View more
  • References (38)
    38 references, page 1 of 4

    [1] N. Alon, D. Moshkovitz, and S. Safra. Algorithmic construction of sets for k-restrictions. ACM Trans. Algorithms, 2(2):153-177, Apr. 2006.

    [2] K. M. Alzoubi, P.-J. Wan, and O. Frieder. Message-optimal connected dominating sets in mobile ad hoc networks. In the Proceedings of the Int'l Symp. on Mobile Ad Hoc Net. and Comput., pages 157-164, 2002.

    [3] K. M. Alzoubi, P.-J. Wan, and O. Frieder. New distributed algorithm for connected dominating set in wireless ad hoc networks. In Proceedings of the 35th Annual Hawaii International Conference on System Sciences (HICSS), pages 3849-3855. IEEE, 2002.

    [4] B. Berger, J. Rompel, and P. W. Shor. Efficient NC algorithms for set cover with applications to learning and geometry. In Proc. of the Symp. on Found. of Comp. Sci. (FOCS), pages 454-477, 1994.

    [5] J. Blum, M. Ding, A. Thaeler, and X. Cheng. Connected dominating set in sensor networks and manets. In Handbook of Combinatorial Optimization, pages 329-369. Springer, 2005.

    [7] X. Cheng, X. Huang, D. Li, W. Wu, and D.-Z. Du. A polynomial-time approximation scheme for the minimum-connected dominating set in ad hoc wireless networks. Networks, 42(4):202- 208, 2003.

    [8] X. Cheng, F. Wang, and D.-Z. Du. Connected dominating set. In Encyclopedia of Algorithms, pages 1-99. Springer, 2008.

    [9] F. Dai and J. Wu. An extended localized algorithm for connected dominating set formation in ad hoc wireless networks. IEEE Transactions on Parallel and Distributed Systems, 15(10):908- 920, 2004.

    [10] B. Das and V. Bharghavan. Routing in ad-hoc networks using minimum connected dominating sets. In Proc. of the IEEE Int'l Conf. on Communications (ICC), volume 1, pages 376-380. IEEE, 1997.

    [11] A. Das Sarma, S. Holzer, L. Kor, A. Korman, D. Nanongkai, G. Pandurangan, D. Peleg, and R. Wattenhofer. Distributed verification and hardness of distributed approximation. In Proc. of the Symp. on Theory of Comp. (STOC), pages 363-372, 2011.

  • Related Organizations (2)
    Purdue University
    United States
    MIT ( MIT )
    United States
    Website url:
  • Metrics
Share - Bookmark