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.