{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,27]],"date-time":"2025-10-27T20:33:27Z","timestamp":1761597207026},"reference-count":34,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2010,6,2]],"date-time":"2010-06-02T00:00:00Z","timestamp":1275436800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2010,11]]},"DOI":"10.1007\/s00224-010-9271-x","type":"journal-article","created":{"date-parts":[[2010,6,1]],"date-time":"2010-06-01T19:25:41Z","timestamp":1275420341000},"page":"811-836","source":"Crossref","is-referenced-by-count":11,"title":["Distributed Approximation of Capacitated Dominating Sets"],"prefix":"10.1007","volume":"47","author":[{"given":"Fabian","family":"Kuhn","sequence":"first","affiliation":[]},{"given":"Thomas","family":"Moscibroda","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2010,6,2]]},"reference":[{"issue":"4","key":"9271_CR1","doi-asserted-by":"crossref","first-page":"567","DOI":"10.1016\/0196-6774(86)90019-2","volume":"7","author":"N. Alon","year":"1986","unstructured":"Alon, N., Babai, L., Itai, A.: A\u00a0fast and simple randomized parallel algorithm for the maximal independent set problem. J.\u00a0Algorithms 7(4), 567\u2013583 (1986)","journal-title":"J.\u00a0Algorithms"},{"key":"9271_CR2","doi-asserted-by":"crossref","unstructured":"Alzoubi, K., Wan, P.-J., Frieder, O.: Message-optimal connected dominating sets in mobile ad hoc networks. In: Proc. of the 3rd ACM Int. Symposium on Mobile Ad Hoc Networking and Computing (MOBIHOC), EPFL Lausanne, Switzerland, pp.\u00a0157\u2013164 (2002)","DOI":"10.1145\/513800.513820"},{"issue":"4","key":"9271_CR3","first-page":"804","volume":"32","author":"B. Awerbuch","year":"1985","unstructured":"Awerbuch, B.: Complexity of network synchronization. J.\u00a0ACM 32(4), 804\u2013823 (1985)","journal-title":"J.\u00a0ACM"},{"issue":"3","key":"9271_CR4","doi-asserted-by":"crossref","first-page":"385","DOI":"10.1006\/jagm.1993.1047","volume":"15","author":"J. Bar-Ilan","year":"1993","unstructured":"Bar-Ilan, J., Kortsarz, G., Peleg, D.: How to allocate network centers. J.\u00a0Algorithms 15(3), 385\u2013415 (1993)","journal-title":"J.\u00a0Algorithms"},{"key":"9271_CR5","doi-asserted-by":"crossref","first-page":"179","DOI":"10.1016\/S0304-3975(99)00130-9","volume":"250","author":"J. Bar-Ilan","year":"2001","unstructured":"Bar-Ilan, J., Kortsarz, G., Peleg, D.: Generalized submodular cover problems and applications. Theor. Comput. Sci. 250, 179\u2013200 (2001)","journal-title":"Theor. Comput. Sci."},{"key":"9271_CR6","doi-asserted-by":"crossref","unstructured":"Birk, Y., Keidar, I., Liss, L., Schuster, A., Wolff, R.: Veracity radius\u2014capturing the locality of distributed computations. In: Proc. of the 25th Annual ACM Symposium on Principles of Distributed Computing (PODC) (2006)","DOI":"10.1145\/1146381.1146399"},{"key":"9271_CR7","doi-asserted-by":"crossref","unstructured":"Chan, H., Luk, M., Perrig, A.: Using clustering information for sensor network localization. In: Proc. of the 1st Conference on Distributed Computing in Sensor Systems (DCOSS) (2005)","DOI":"10.1007\/11502593_11"},{"issue":"10","key":"9271_CR8","first-page":"902","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 Trans. Parallel Distrib. Syst. 15(10), 902\u2013920 (2004)","journal-title":"IEEE Trans. Parallel Distrib. Syst."},{"key":"9271_CR9","doi-asserted-by":"crossref","unstructured":"Deb, B., Nath, B.: On the node-scheduling approach to topology control in ad hoc networks. In: Proceedings of the 6th ACM International Symposium on Mobile Ad Hoc Networking and Computing (MOBIHOC), pp.\u00a014\u201326 (2005)","DOI":"10.1145\/1062689.1062693"},{"issue":"4","key":"9271_CR10","doi-asserted-by":"crossref","first-page":"40","DOI":"10.1145\/1054916.1054931","volume":"35","author":"M. Elkin","year":"2004","unstructured":"Elkin, M.: Distributed approximation\u2014a survey. ACM SIGACT News\u2014Distrib. Comput. Column 35(4), 40\u201357 (2004)","journal-title":"ACM SIGACT News\u2014Distrib. Comput. Column"},{"key":"9271_CR11","doi-asserted-by":"crossref","unstructured":"Gandhi, R., Parthasarathy, S.: Distributed algorithms for coloring and connected domination in wireless ad hoc networks. In: Foundations of Software Technology and Theoretical Computer Science (FSTTCS) (2004)","DOI":"10.1007\/978-3-540-30538-5_37"},{"key":"9271_CR12","doi-asserted-by":"crossref","unstructured":"Gao, J., Guibas, L., Hershberger, J., Zhang, L., Zhu, A.: Discrete mobile centers. In: Proc. 17th Symposium on Computational Geometry (SCG), pp.\u00a0188\u2013196 (2001)","DOI":"10.1145\/378583.378666"},{"key":"9271_CR13","volume-title":"Computers and Intractability, A Guide to the Theory of NP-Completeness","author":"M.R. Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability, A Guide to the Theory of NP-Completeness. Freeman, New York (1979)"},{"key":"9271_CR14","doi-asserted-by":"crossref","unstructured":"Gfeller, B., Vicari, E.: A randomized distributed algorithm for the maximal independent set problem in growth-bounded graphs. In: Proceedings of the 26th ACM Symposium on Principles of Distributed Computing (PODC), pp.\u00a053\u201360 (2007)","DOI":"10.1145\/1281100.1281111"},{"key":"9271_CR15","doi-asserted-by":"crossref","unstructured":"Grandoni, F., Kr\u00f6nemann, J., Panconesi, A., Sozio, M.: Primal-dual based distributed algorithms for vertex cover with semi-hard capacities. In: Proc. of the 24th Annual ACM Symposium on Principles of Distributed Computing (PODC), pp.\u00a0118\u2013125 (2005)","DOI":"10.1145\/1073814.1073835"},{"key":"9271_CR16","first-page":"8020","volume-title":"Proceedings of the 33rd Hawaii International Conference on System Sciences (HICSS)","author":"W.R. Heinzelman","year":"2000","unstructured":"Heinzelman, W.R., Chandrakasan, A., Balakrishnan, H.: Energy-efficient communication protocol for wireless microsensor networks. In: Proceedings of the 33rd Hawaii International Conference on System Sciences (HICSS), p.\u00a08020. IEEE Comput. Soc., Los Alamitos (2000)"},{"key":"9271_CR17","unstructured":"Jia, L., Rajaraman, R., Suel, R.: An efficient distributed algorithm for constructing small dominating sets. In: Proc. of the 20th ACM Symposium on Principles of Distributed Computing (PODC), pp.\u00a033\u201342 (2001)"},{"key":"9271_CR18","doi-asserted-by":"crossref","unstructured":"Kuhn, F., Moscibroda, T., Wattenhofer, R.: What cannot be computed locally! In: Proceedings of 23rd ACM Symposium on Principles of Distributed Computing (PODC), pp.\u00a0300\u2013309 (2004)","DOI":"10.1145\/1011767.1011811"},{"key":"9271_CR19","doi-asserted-by":"crossref","unstructured":"Kuhn, F., Moscibroda, T., Wattenhofer, R.: The locality of bounded growth. In: Proc. of the 24th ACM Symp. on Principles of Distributed Computing (PODC) (2005)","DOI":"10.1145\/1073814.1073826"},{"key":"9271_CR20","doi-asserted-by":"crossref","unstructured":"Kuhn, F., Moscibroda, T., Wattenhofer, R.: The price of being near-sighted. In: Proc. of the 17th ACM-SIAM Symposium on Discrete Algorithms (SODA) (2006)","DOI":"10.1145\/1109557.1109666"},{"key":"9271_CR21","doi-asserted-by":"crossref","unstructured":"Kuhn, F., Moscriboda, T., Nieberg, T., Wattenhofer, R.: Fast deterministic distributed maximal independent set computation on growth-bounded graphs. In: Proc. 19th Symposium on Distributed Computing (DISC) (2005)","DOI":"10.1007\/11561927_21"},{"issue":"4","key":"9271_CR22","doi-asserted-by":"crossref","first-page":"303","DOI":"10.1007\/s00446-004-0112-5","volume":"17","author":"F. Kuhn","year":"2005","unstructured":"Kuhn, F., Wattenhofer, R.: Constant-time distributed dominating set approximation. Distrib. Comput. J. 17(4), 303\u2013310 (2005)","journal-title":"Distrib. Comput. J."},{"key":"9271_CR23","doi-asserted-by":"crossref","first-page":"40","DOI":"10.1006\/jagm.1998.0929","volume":"28","author":"S. Kutten","year":"1998","unstructured":"Kutten, S., Peleg, D.: Fast distributed construction of small k-dominating sets and applications. J.\u00a0Algorithms 28, 40\u201366 (1998)","journal-title":"J.\u00a0Algorithms"},{"key":"9271_CR24","doi-asserted-by":"crossref","unstructured":"Lenzen, C., Wattenhofer, R.: Leveraging Linial\u2019s locality limit. In: Proc. of 22nd Symposium on Distributed Computing (DISC), Arcachon, France, September 2008","DOI":"10.1007\/978-3-540-87779-0_27"},{"issue":"1","key":"9271_CR25","doi-asserted-by":"crossref","first-page":"193","DOI":"10.1137\/0221015","volume":"21","author":"N. Linial","year":"1992","unstructured":"Linial, N.: Locality in distributed graph algorithms. SIAM J. Comput. 21(1), 193\u2013201 (1992)","journal-title":"SIAM J. Comput."},{"issue":"4","key":"9271_CR26","doi-asserted-by":"crossref","first-page":"441","DOI":"10.1007\/BF01303516","volume":"13","author":"N. Linial","year":"1993","unstructured":"Linial, N., Saks, M.: Low diameter graph decompositions. Combinatorica 13(4), 441\u2013454 (1993)","journal-title":"Combinatorica"},{"key":"9271_CR27","doi-asserted-by":"crossref","first-page":"1036","DOI":"10.1137\/0215074","volume":"15","author":"M. Luby","year":"1986","unstructured":"Luby, M.: A simple parallel algorithm for the maximal independent set problem. SIAM J. Comput. 15, 1036\u20131053 (1986)","journal-title":"SIAM J. Comput."},{"key":"9271_CR28","doi-asserted-by":"crossref","unstructured":"Moscibroda, T., Wattenhofer, R.: Maximal independent sets in radio networks. In: Proc. of the 23rd ACM Symp. on Principles of Distributed Computing (PODC) (2005)","DOI":"10.1145\/1073814.1073842"},{"issue":"6","key":"9271_CR29","doi-asserted-by":"crossref","first-page":"1259","DOI":"10.1137\/S0097539793254571","volume":"24","author":"M. Naor","year":"1995","unstructured":"Naor, M., Stockmeyer, L.: What can be computed locally? SIAM J. Comput. 24(6), 1259\u20131277 (1995)","journal-title":"SIAM J. Comput."},{"issue":"4","key":"9271_CR30","doi-asserted-by":"crossref","first-page":"365","DOI":"10.1007\/BF02579324","volume":"7","author":"P. Raghavan","year":"1987","unstructured":"Raghavan, P., Thompson, C.D.: Randomized rounding: A technique for provably good algorithms and algorithmic proofs. Combinatorica 7(4), 365\u2013374 (1987)","journal-title":"Combinatorica"},{"key":"9271_CR31","doi-asserted-by":"crossref","unstructured":"Schneider, J., Wattenhofer, R.: A log-star distributed maximal independent set algorithm for growth-bounded graphs. In: Proceedings of the 27th ACM Symposium on Principles of Distributed Computing (PODC) (2008)","DOI":"10.1145\/1400751.1400758"},{"key":"9271_CR32","doi-asserted-by":"crossref","unstructured":"Wan, P., Alzoubi, K., Frieder, O.: Distributed construction of connected dominating set in wireless ad hoc networks. In: Proceedings of INFOCOM (2002)","DOI":"10.1145\/513819.513820"},{"key":"9271_CR33","doi-asserted-by":"crossref","unstructured":"Wang, Y., Wang, W., Li, X.-Y.: Distributed low-cost backbone formation for wireless ad hoc networks. In: Proceedings of the 6th ACM International Symposium on Mobile Ad Hoc Networking and Computing (MOBIHOC), pp.\u00a02\u201313 (2005)","DOI":"10.1145\/1062689.1062692"},{"key":"9271_CR34","doi-asserted-by":"crossref","unstructured":"Wu, J., Li, H.: On calculating connected dominating set for efficient routing in ad hoc wireless networks. In: Proc. of the 3rd Int. Workshop on Discrete Algorithms and Methods for Mobile Computing and Communications (DIALM), pp.\u00a07\u201314 (1999)","DOI":"10.1145\/313239.313261"}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-010-9271-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00224-010-9271-x\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-010-9271-x","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,29]],"date-time":"2019-05-29T18:52:55Z","timestamp":1559155975000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00224-010-9271-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,6,2]]},"references-count":34,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2010,11]]}},"alternative-id":["9271"],"URL":"https:\/\/doi.org\/10.1007\/s00224-010-9271-x","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"value":"1432-4350","type":"print"},{"value":"1433-0490","type":"electronic"}],"subject":[],"published":{"date-parts":[[2010,6,2]]}}}