{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,22]],"date-time":"2026-01-22T02:16:06Z","timestamp":1769048166029,"version":"3.49.0"},"publisher-location":"Berlin, Heidelberg","reference-count":40,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783662439500","type":"print"},{"value":"9783662439517","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2014]]},"DOI":"10.1007\/978-3-662-43951-7_41","type":"book-chapter","created":{"date-parts":[[2014,6,11]],"date-time":"2014-06-11T08:37:49Z","timestamp":1402475869000},"page":"483-494","source":"Crossref","is-referenced-by-count":6,"title":["Near-Optimal Distributed Approximation of Minimum-Weight Connected Dominating Set"],"prefix":"10.1007","author":[{"given":"Mohsen","family":"Ghaffari","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"2","key":"41_CR1","doi-asserted-by":"publisher","first-page":"153","DOI":"10.1145\/1150334.1150336","volume":"2","author":"N. Alon","year":"2006","unstructured":"Alon, N., Moshkovitz, D., Safra, S.: Algorithmic construction of sets for k-restrictions. ACM Trans. Algorithms\u00a02(2), 153\u2013177 (2006)","journal-title":"ACM Trans. Algorithms"},{"key":"41_CR2","doi-asserted-by":"crossref","unstructured":"Alzoubi, K.M., Wan, P.-J., Frieder, O.: Message-optimal connected dominating sets in mobile ad hoc networks. In: the Proceedings of the Int\u2019l Symp. on Mobile Ad Hoc Net. and Comput, pp. 157\u2013164 (2002)","DOI":"10.1145\/513819.513820"},{"key":"41_CR3","doi-asserted-by":"crossref","unstructured":"Alzoubi, K.M., Wan, P.-J., Frieder, O.: 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), pp. 3849\u20133855. IEEE (2002)","DOI":"10.1109\/HICSS.2002.994519"},{"key":"41_CR4","doi-asserted-by":"crossref","unstructured":"Berger, B., Rompel, J., Shor, P.W.: Efficient NC algorithms for set cover with applications to learning and geometry. In: Proc. of the Symp. on Found. of Comp. Sci. (FOCS), pp. 454\u2013477 (1994)","DOI":"10.1016\/S0022-0000(05)80068-6"},{"key":"41_CR5","doi-asserted-by":"crossref","unstructured":"Blum, J., Ding, M., Thaeler, A., Cheng, X.: Connected dominating set in sensor networks and manets. In: Handbook of Combinatorial Optimization, pp. 329\u2013369. Springer (2005)","DOI":"10.1007\/0-387-23830-1_8"},{"key":"41_CR6","doi-asserted-by":"crossref","unstructured":"Chen, Y.P., Liestman, A.L.: Approximating minimum size weakly-connected dominating sets for clustering mobile ad hoc networks. In: Proceedings of the 3rd ACM International Symposium on Mobile ad Hoc Networking & Computing, pp. 165\u2013172. ACM (2002)","DOI":"10.1145\/513819.513821"},{"issue":"4","key":"41_CR7","doi-asserted-by":"crossref","first-page":"202","DOI":"10.1002\/net.10097","volume":"42","author":"X. Cheng","year":"2003","unstructured":"Cheng, X., Huang, X., Li, D., Wu, W., Du, D.-Z.: A polynomial-time approximation scheme for the minimum-connected dominating set in ad hoc wireless networks. Networks\u00a042(4), 202\u2013208 (2003)","journal-title":"Networks"},{"key":"41_CR8","doi-asserted-by":"crossref","unstructured":"Cheng, X., Wang, F., Du., D.-Z.: Connected dominating set. In: Encyclopedia of Algorithms, pp. 1\u201399. Springer (2008)","DOI":"10.1007\/978-0-387-30162-4_89"},{"issue":"10","key":"41_CR9","doi-asserted-by":"publisher","first-page":"908","DOI":"10.1109\/TPDS.2004.48","volume":"15","author":"F. Dai","year":"2004","unstructured":"Dai, F., Wu, J.: An extended localized algorithm for connected dominating set formation in ad hoc wireless networks. IEEE Transactions on Parallel and Distributed Systems\u00a015(10), 908\u2013920 (2004)","journal-title":"IEEE Transactions on Parallel and Distributed Systems"},{"key":"41_CR10","doi-asserted-by":"crossref","unstructured":"Das, B., Bharghavan, V.: Routing in ad-hoc networks using minimum connected dominating sets. In: Proc. of the IEEE Int\u2019l Conf. on Communications (ICC), vol. 1, pp. 376\u2013380. IEEE (1997)","DOI":"10.1109\/ICC.1997.605303"},{"key":"41_CR11","doi-asserted-by":"crossref","unstructured":"Das Sarma, A., Holzer, S., Kor, L., Korman, A., Nanongkai, D., Pandurangan, G., Peleg, D., Wattenhofer, R.: Distributed verification and hardness of distributed approximation. In: Proc. of the Symp. on Theory of Comp. (STOC), pp. 363\u2013372 (2011)","DOI":"10.1145\/1993636.1993686"},{"key":"41_CR12","doi-asserted-by":"crossref","unstructured":"Das Sarma, A., Nanongkai, D., Pandurangan, G.: Fast distributed random walks. In: The Proc. of the Int\u2019l Symp. on Princ. of Dist. Comp. (PODC), pp. 161\u2013170 (2009)","DOI":"10.1145\/1582716.1582745"},{"key":"41_CR13","doi-asserted-by":"crossref","unstructured":"Das Sarma, A., Nanongkai, D., Pandurangan, G., Tetali, P.: Efficient distributed random walks with applications. In: The Proc. of the Int\u2019l Symp. on Princ. of Dist. Comp. (PODC), pp. 201\u2013210 (2010)","DOI":"10.1145\/1835698.1835745"},{"key":"41_CR14","unstructured":"Dubhashi, D., Mei, A., Panconesi, A., Radhakrishnan, J., Srinivasan, A.: Fast distributed algorithms for (weakly) connected dominating sets and linear-size skeletons. In: Pro. of ACM-SIAM Symp. on Disc. Alg. (SODA), pp. 717\u2013724 (2003)"},{"key":"41_CR15","doi-asserted-by":"crossref","unstructured":"Elkin, M.: 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), pp. 331\u2013340 (2004)","DOI":"10.1145\/1007352.1007407"},{"key":"41_CR16","doi-asserted-by":"crossref","unstructured":"Feige, U.: A threshold of ln n for approximating set cover (preliminary version). In: Proc. of the Symp. on Theory of Comp. (STOC), pp. 314\u2013318 (1996)","DOI":"10.1145\/237814.237977"},{"key":"41_CR17","doi-asserted-by":"crossref","unstructured":"Frischknecht, S., Holzer, S., Wattenhofer, R.: Networks cannot compute their diameter in sublinear time. In: Pro. of ACM-SIAM Symp. on Disc. Alg. (SODA), pp. 1150\u20131162 (2012)","DOI":"10.1137\/1.9781611973099.91"},{"key":"41_CR18","unstructured":"Garay, J., Kutten, S., Peleg, D.: A sub-linear time distributed algorithm for minimum-weight spanning trees. In: Proc. of the Symp. on Found. of Comp. Sci. FOCS (1993)"},{"key":"41_CR19","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability; A Guide to the Theory of NP-Completeness. W. H. Freeman & Co., New York (1990)"},{"key":"41_CR20","unstructured":"Ghaffari, M.: Near-optimal distributed approximation of minimum-weight connected dominating set, http:\/\/people.csail.mit.edu\/ghaffari\/papers\/CDS.pdf"},{"key":"41_CR21","doi-asserted-by":"crossref","unstructured":"Ghaffari, M., Kuhn, F.: Distributed minimum cut approximation. In: Proc. of the Int\u2019l Symp. on Dist. Comp. (DISC), pp. 1\u201315 (2013)","DOI":"10.1007\/978-3-642-41527-2_1"},{"issue":"4","key":"41_CR22","doi-asserted-by":"publisher","first-page":"374","DOI":"10.1007\/PL00009201","volume":"20","author":"S. Guha","year":"1998","unstructured":"Guha, S., Khuller, S.: Approximation algorithms for connected dominating sets. Algorithmica\u00a020(4), 374\u2013387 (1998)","journal-title":"Algorithmica"},{"issue":"1","key":"41_CR23","doi-asserted-by":"publisher","first-page":"57","DOI":"10.1006\/inco.1998.2754","volume":"150","author":"S. Guha","year":"1999","unstructured":"Guha, S., Khuller, S.: Improved methods for approximating node weighted steiner trees and connected dominating sets. Information and computation\u00a0150(1), 57\u201374 (1999)","journal-title":"Information and computation"},{"key":"41_CR24","doi-asserted-by":"crossref","unstructured":"Holzer, S., Wattenhofer, R.: Optimal distributed all pairs shortest paths and applications. In: The Proc. of the Int\u2019l Symp. on Princ. of Dist. Comp. (PODC), pp. 355\u2013364 (2012)","DOI":"10.1145\/2332432.2332504"},{"key":"41_CR25","unstructured":"Jia, L., Rajaraman, R., Suel, T.: An efficient distributed algorithm for constructing small dominating sets. In: The Proc. of the Int\u2019l Symp. on Princ. of Dist. Comp. (PODC), pp. 32\u201342 (2001)"},{"issue":"1","key":"41_CR26","doi-asserted-by":"crossref","first-page":"104","DOI":"10.1006\/jagm.1995.1029","volume":"19","author":"P. Klein","year":"1995","unstructured":"Klein, P., Ravi, R.: A nearly best-possible approximation algorithm for node-weighted steiner trees. Journal of Algorithms\u00a019(1), 104\u2013115 (1995)","journal-title":"Journal of Algorithms"},{"key":"41_CR27","doi-asserted-by":"crossref","unstructured":"Kuhn, F., Moscibroda, T., Wattenhofer, R.: What cannot be computed locally? In: The Proc. of the Int\u2019l Symp. on Princ. of Dist. Comp. (PODC), pp. 300\u2013309 (2004)","DOI":"10.1145\/1011767.1011811"},{"key":"41_CR28","doi-asserted-by":"crossref","unstructured":"Kuhn, F., Wattenhofer, R.: Constant-time distributed dominating set approximation. In: The Proc. of the Int\u2019l Symp. on Princ. of Dist. Comp. (PODC), pp. 25\u201332 (2003)","DOI":"10.1145\/872035.872040"},{"key":"41_CR29","doi-asserted-by":"crossref","unstructured":"Kutten, S., Peleg, D.: Fast distributed construction of k-dominating sets and applications. In: The Proc. of the Int\u2019l Symp. on Princ. of Dist. Comp. (PODC), pp. 238\u2013251 (1995)","DOI":"10.1145\/224964.224990"},{"key":"41_CR30","doi-asserted-by":"crossref","unstructured":"Lenzen, C., Patt-Shamir, B.: Fast routing table construction using small messages: Extended abstract. In: Proc. of the Symp. on Theory of Comp. (STOC), pp. 381\u2013390 (2013)","DOI":"10.1145\/2488608.2488656"},{"issue":"1","key":"41_CR31","doi-asserted-by":"crossref","first-page":"111","DOI":"10.1007\/s10898-005-8466-1","volume":"35","author":"M. Min","year":"2006","unstructured":"Min, M., Du, H., Jia, X., Huang, C.X., Huang, S.C.-H., Wu, W.: Improving construction for connected dominating set with steiner tree in wireless sensor networks. Journal of Global Optimization\u00a035(1), 111\u2013119 (2006)","journal-title":"Journal of Global Optimization"},{"key":"41_CR32","doi-asserted-by":"crossref","unstructured":"Nanongkai, D.: Distributed approximation algorithms for weighted shortest paths. In: Proc. of the Symp. on Theory of Comp. (STOC) (to appear, 2014)","DOI":"10.1145\/2591796.2591850"},{"key":"41_CR33","doi-asserted-by":"crossref","unstructured":"Nanongkai, D., Das Sarma, A., Pandurangan, G.: A tight unconditional lower bound on distributed randomwalk computation. In: The Proc. of the Int\u2019l Symp. on Princ. of Dist. Comp. (PODC), pp. 257\u2013266 (2011)","DOI":"10.1145\/1993806.1993853"},{"key":"41_CR34","doi-asserted-by":"crossref","unstructured":"Peleg, D.: Distributed Computing: A Locality-sensitive Approach. In: Society for Industrial and Applied Mathematics, Philadelphia, PA, USA (2000)","DOI":"10.1137\/1.9780898719772"},{"key":"41_CR35","doi-asserted-by":"crossref","unstructured":"Peleg, D., Rubinovich, V.: A near-tight lower bound on the time complexity of distributed MST construction. In: Proc. of the Symp. on Found. of Comp. Sci. (FOCS), p. 253 (1999)","DOI":"10.1109\/SFFCS.1999.814597"},{"key":"41_CR36","doi-asserted-by":"crossref","unstructured":"Pettie, S.: Distributed algorithms for ultrasparse spanners and linear size skeletons. In: The Proc. of the Int\u2019l Symp. on Princ. of Dist. Comp. (PODC), pp. 253\u2013262 (2008)","DOI":"10.1145\/1400751.1400786"},{"key":"41_CR37","doi-asserted-by":"crossref","unstructured":"Raz, R., Safra, S.: A sub-constant error-probability low-degree test, and a sub-constant error-probability PCP characterization of NP. In: Proc. of the Symp. on Theory of Comp. (STOC), pp. 475\u2013484 (1997)","DOI":"10.1145\/258533.258641"},{"key":"41_CR38","doi-asserted-by":"crossref","unstructured":"Thurimella, R.: Sub-linear distributed algorithms for sparse certificates and biconnected components. In: The Proc. of the Int\u2019l Symp. on Princ. of Dist. Comp. (PODC), pp. 28\u201337 (1995)","DOI":"10.1145\/224964.224968"},{"key":"41_CR39","doi-asserted-by":"crossref","unstructured":"Wan, P.-J., Alzoubi, K.M., Frieder, O.: Distributed construction of connected dominating set in wireless ad hoc networks. In: The Proc. of IEEE Int\u2019l Conf. on Computer Communications (INFOCOM), vol.\u00a03, pp. 1597\u20131604 (2002)","DOI":"10.1109\/INFCOM.2002.1019411"},{"key":"41_CR40","doi-asserted-by":"crossref","unstructured":"Wu, J., Gao, M., Stojmenovic, I.: On calculating power-aware connected dominating sets for efficient routing in ad hoc wireless networks. In: IEEE\u2019s International Conference on Parallel Processing (ICPP), pp. 346\u2013354 (2001)","DOI":"10.1109\/ICPP.2001.952080"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages, and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-662-43951-7_41","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,5,3]],"date-time":"2025-05-03T09:23:37Z","timestamp":1746264217000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-662-43951-7_41"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014]]},"ISBN":["9783662439500","9783662439517"],"references-count":40,"URL":"https:\/\/doi.org\/10.1007\/978-3-662-43951-7_41","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014]]}}}