publication . Preprint . 2014

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

Ghaffari, Mohsen;
Open Access English
  • Published: 29 Apr 2014
Abstract
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$ is the number of nodes. MCDS is a classical NP-hard problem and the achieved approximation factor $O(\log n)$ is known to be optimal up to a constant factor, unless P=NP. Furthermore, the $\tilde{O}(D+\sqrt{n})$ round complexity is known to be optimal modulo logarithmic factors (for any approximation), following [Das Sarma et al.---STOC'11].
Subjects
ACM Computing Classification System: MathematicsofComputing_DISCRETEMATHEMATICS
free text keywords: Computer Science - Data Structures and Algorithms, Computer Science - Distributed, Parallel, and Cluster Computing
Related Organizations
Funded by
NSF| Emerging Frontiers of Science of Information
Project
  • Funder: National Science Foundation (NSF)
  • Project Code: 0939370
  • Funding stream: Directorate for Computer & Information Science & Engineering | Division of Computing and Communication Foundations
,
NSF| AF: Small: Bounded-Contention Coding for Wireless Networks
Project
  • Funder: National Science Foundation (NSF)
  • Project Code: 1217506
  • Funding stream: Directorate for Computer & Information Science & Engineering | Division of Computing and Communication Foundations
,
NSF| CCF-AF: Abstract Medium Access Control Layers
Project
  • Funder: National Science Foundation (NSF)
  • Project Code: 0937274
  • Funding stream: Directorate for Computer & Information Science & Engineering | Division of Computing and Communication Foundations
Download from
38 references, page 1 of 3

[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. [OpenAIRE]

[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. [OpenAIRE]

[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. [OpenAIRE]

[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.

[12] A. Das Sarma, D. Nanongkai, and G. Pandurangan. Fast distributed random walks. In the Proc. of the Int'l Symp. on Princ. of Dist. Comp. (PODC), pages 161-170, 2009. [OpenAIRE]

[13] A. Das Sarma, D. Nanongkai, G. Pandurangan, and P. Tetali. Efficient distributed random walks with applications. In the Proc. of the Int'l Symp. on Princ. of Dist. Comp. (PODC), pages 201-210, 2010.

[14] D. Dubhashi, A. Mei, A. Panconesi, J. Radhakrishnan, and A. Srinivasan. Fast distributed algorithms for (weakly) connected dominating sets and linear-size skeletons. In Pro. of ACMSIAM Symp. on Disc. Alg. (SODA), pages 717-724, 2003. [OpenAIRE]

[15] M. Elkin. Unconditional lower bounds on the time-approximation tradeoffs for the distributed minimum spanning tree problem. In Proc. of the Symp. on Theory of Comp. (STOC), pages 331-340, 2004.

[16] U. Feige. A threshold of ln n for approximating set cover (preliminary version). In Proc. of the Symp. on Theory of Comp. (STOC), pages 314-318, 1996.

38 references, page 1 of 3
Powered by OpenAIRE Research Graph
Any information missing or wrong?Report an Issue