{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,27]],"date-time":"2025-03-27T10:43:41Z","timestamp":1743072221839,"version":"3.40.3"},"publisher-location":"Boston, MA","reference-count":25,"publisher":"Springer US","isbn-type":[{"type":"print","value":"9780387307701"},{"type":"electronic","value":"9780387301624"}],"license":[{"start":{"date-parts":[[2008,1,1]],"date-time":"2008-01-01T00:00:00Z","timestamp":1199145600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2008,1,1]],"date-time":"2008-01-01T00:00:00Z","timestamp":1199145600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2008]]},"DOI":"10.1007\/978-0-387-30162-4_89","type":"book-chapter","created":{"date-parts":[[2008,6,26]],"date-time":"2008-06-26T18:36:50Z","timestamp":1214505410000},"page":"191-195","source":"Crossref","is-referenced-by-count":2,"title":["Connected Dominating Set"],"prefix":"10.1007","author":[{"given":"Xiuzhen","family":"Cheng","sequence":"first","affiliation":[]},{"given":"Feng","family":"Wang","sequence":"additional","affiliation":[]},{"given":"Ding-Zhu","family":"Du","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"89_CR1_89","doi-asserted-by":"crossref","unstructured":"Alzoubi, K.M., Wan, P.-J., Frieder, O.: Message\u2010optimal connected dominating sets in mobile ad hoc networks. In: ACM MOBIHOC, Lausanne, Switzerland, 09\u201311 June 2002","DOI":"10.1145\/513800.513820"},{"key":"89_CR2_89","doi-asserted-by":"crossref","unstructured":"Alzoubi, K.M., P.-J.Wan, Frieder, O.: New Distributed Algorithm for Connected Dominating Set in Wireless Ad Hoc Networks. In: HICSS35, Hawaii, January 2002","DOI":"10.1145\/513800.513820"},{"key":"89_CR3_89","volume-title":"LNCS, vol. 4110, pp 3\u201314","author":"C. Ambuhl","year":"2006","unstructured":"Ambuhl, C., Erlebach, T., Mihalak, M., Nunkesser, M.: Constant\u2010Factor Approximation for Minimum\u2010Weight (Connected) Dominating Sets in Unit Disk Graphs. In: LNCS, vol.\u00a04110, pp 3\u201314. Springer, Berlin (2006)"},{"key":"89_CR4_89","doi-asserted-by":"crossref","unstructured":"Blum, J., Ding, M., Thaeler, A., Cheng, X.: Applications of Connected Dominating Sets in Wireless Networks. In: Du, D.-Z., Pardalos, P. (eds.) Handbook of Combinatorial Optimization, pp.\u00a0329\u2013369. Kluwer Academic (2004)","DOI":"10.1007\/0-387-23830-1_8"},{"key":"89_CR5_89","doi-asserted-by":"publisher","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\u00a0polynomial-time approximation scheme for minimum connected dominating set in ad hoc wireless networks. Networks 42, 202\u2013208 (2003)","journal-title":"Networks"},{"key":"89_CR6_89","first-page":"167","volume-title":"Proceedings of 19th ACM-SIAM Symposium on Discrete Algorithms (SODA)","author":"D.Z. Du","year":"2008","unstructured":"Du, D.-Z., Graham, R.L., Pardalos, P.M., Wan, P.-J., Wu, W., Zhao, W.: Analysis of greedy approximations with nonsubmodular potential functions. In: Proceedings of the 19th annual ACM-SIAM Symposium on Discrete Algorithms (SODA) pp.\u00a0167\u2013175. January 2008"},{"key":"89_CR7_89","unstructured":"Dubhashi, D., Mei, A., Panconesi, A., Radhakrishnan, J., Srinivasan, A.: Fast Distributed Algorithms for (Weakly) Connected Dominating Sets and Linear-Size Skeletons. In: SODA, 2003, pp.\u00a0717\u2013724"},{"issue":"4","key":"89_CR8_89","doi-asserted-by":"crossref","first-page":"634","DOI":"10.1145\/285055.285059","volume":"45","author":"U. Feige","year":"1998","unstructured":"Feige, U.: A\u00a0Threshold of $$ { \\ln n } $$ for Approximating Set Cover. J.\u00a0ACM 45(4) 634\u2013652 (1998)","journal-title":"J. ACM"},{"key":"89_CR9_89","doi-asserted-by":"crossref","unstructured":"Gfeller, B., Vicari, E.: A\u00a0Randomized Distributed Algorithm for the Maximal Independent Set Problem in Growth\u2010Bounded Graphs. In: PODC 2007","DOI":"10.1145\/1281100.1281111"},{"key":"89_CR10_89","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 20, 374\u2013387 (1998)","journal-title":"Algorithmica"},{"key":"89_CR11_89","doi-asserted-by":"crossref","unstructured":"Jia, L., Rajaraman, R., Suel, R.: An Efficient Distributed Algorithm for Constructing Small Dominating Sets. In: PODC, Newport, Rhode Island, USA, August 2001","DOI":"10.1007\/s00446-002-0078-0"},{"key":"89_CR12_89","doi-asserted-by":"crossref","unstructured":"Kuhn, F., Moscibroda, T., Nieberg, T., Wattenhofer, R.: Fast Deterministic Distributed Maximal Independent Set Computation on Growth\u2010Bounded Graphs. In: DISC, Cracow, Poland, September 2005","DOI":"10.1007\/11561927_21"},{"key":"89_CR13_89","doi-asserted-by":"crossref","unstructured":"Kuhn, F., Moscibroda, T., Nieberg, T., Wattenhofer, R.: Local Approximation Schemes for Ad Hoc and Sensor Networks. In: DIALM-POMC, Cologne, Germany, September 2005","DOI":"10.1145\/1080810.1080827"},{"key":"89_CR14_89","doi-asserted-by":"crossref","unstructured":"Kuhn, F., Moscibroda, T., Wattenhofer, R.: On the Locality of Bounded Growth. In: PODC, Las Vegas, Nevada, USA, July 2005","DOI":"10.1145\/1073814.1073826"},{"key":"89_CR15_89","doi-asserted-by":"crossref","unstructured":"Kuhn, F., Wattenhofer, R.: Constant-Time Distributed Dominating Set Approximation. In: PODC, Boston, Massachusetts, USA, July 2003","DOI":"10.1145\/872035.872040"},{"issue":"1","key":"89_CR16_89","doi-asserted-by":"publisher","first-page":"193","DOI":"10.1137\/0221015","volume":"21","author":"N. Linial","year":"1992","unstructured":"Linial, N.: Locality in distributed graph algorithms. SIAM J.\u00a0Comput. 21(1), 193\u2013201 (1992)","journal-title":"SIAM J. Comput."},{"key":"89_CR17_89","doi-asserted-by":"publisher","first-page":"1036","DOI":"10.1137\/0215074","volume":"15","author":"M. Luby","year":"1986","unstructured":"Luby, M.: A\u00a0Simple Parallel Algorithm for the Maximal Independent Set Problem. SIAM J.\u00a0Comput. 15, 1036\u20131053 (1986)","journal-title":"SIAM J. Comput."},{"key":"89_CR18_89","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1002\/net.3230250205","volume":"25","author":"M.V. Marathe","year":"1995","unstructured":"Marathe, M.V., Breu, H., Hunt III, H.B., Ravi, S.S., Rosenkrantz, D.J.: Simple Heuristics for Unit Disk Graphs. Networks 25, 59\u201368 (1995)","journal-title":"Networks"},{"key":"89_CR19_89","doi-asserted-by":"publisher","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, X., Huang, C.-H., Wu, W.: Improving construction for connected dominating set with Steiner tree in wireless sensor networks. J.\u00a0Glob. Optim. 35, 111\u2013119 (2006)","journal-title":"J. Glob. Optim."},{"key":"89_CR20_89","volume-title":"A PTAS for the Minimum Dominating Set Problem in Unit Disk Graphs. LNCS, vol. 3879, pp. 296\u2013306","author":"T. Nieberg","year":"2006","unstructured":"Nieberg, T., Hurink, J.L.: A\u00a0PTAS for the Minimum Dominating Set Problem in Unit Disk Graphs. LNCS, vol.\u00a03879, pp.\u00a0296\u2013306. Springer, Berlin (2006)"},{"key":"89_CR21_89","doi-asserted-by":"publisher","first-page":"325","DOI":"10.1016\/j.tcs.2004.08.013","volume":"329","author":"L. Ruan","year":"2004","unstructured":"Ruan, L., Du, H., Jia, X., Wu, W., Li, Y., Ko, K.-I.: A\u00a0greedy approximation for minimum connected dominating set. Theor. Comput. Sci. 329, 325\u2013330 (2004)","journal-title":"Theor. Comput. Sci."},{"key":"89_CR22_89","first-page":"607","volume":"13","author":"E. Sampathkumar","year":"1979","unstructured":"Sampathkumar, E., Walikar, H.B.: The Connected Domination Number of a\u00a0Graph. J.\u00a0Math. Phys. Sci. 13, 607\u2013613 (1979)","journal-title":"J. Math. Phys. Sci."},{"issue":"7","key":"89_CR23_89","doi-asserted-by":"publisher","first-page":"721","DOI":"10.1109\/TMC.2007.1034","volume":"6","author":"M.T. Thai","year":"2007","unstructured":"Thai, M.T., Wang F., Liu, D., Zhu, S., Du, D.-Z.: Connected Dominating Sets in Wireless Networks with Different Transmission Range. IEEE Trans. Mob. Comput. 6(7), 721\u2013730 (2007)","journal-title":"IEEE Trans. Mob. Comput."},{"key":"89_CR24_89","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: IEEE INFOCOM 2002","DOI":"10.1145\/513800.513820"},{"key":"89_CR25_89","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.tcs.2005.08.037","volume":"352","author":"W. Wu","year":"2006","unstructured":"Wu, W., Du, H., Jia, X., Li, Y., Huang, C.-H.: Minimum Connected Dominating Sets and Maximal Independent Sets in Unit Disk Graphs. Theor. Comput. Sci. 352, 1\u20137 (2006)","journal-title":"Theor. Comput. Sci."}],"container-title":["Encyclopedia of Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-0-387-30162-4_89","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,9,3]],"date-time":"2022-09-03T02:06:23Z","timestamp":1662170783000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-0-387-30162-4_89"}},"subtitle":["2003; Cheng, Huang, Li, Wu, Du"],"short-title":[],"issued":{"date-parts":[[2008]]},"ISBN":["9780387307701","9780387301624"],"references-count":25,"URL":"https:\/\/doi.org\/10.1007\/978-0-387-30162-4_89","relation":{},"subject":[],"published":{"date-parts":[[2008]]}}}