{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,28]],"date-time":"2026-04-28T19:30:54Z","timestamp":1777404654315,"version":"3.51.4"},"reference-count":12,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2011,4,15]],"date-time":"2011-04-15T00:00:00Z","timestamp":1302825600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2011,12]]},"DOI":"10.1007\/s00453-011-9512-7","type":"journal-article","created":{"date-parts":[[2011,4,14]],"date-time":"2011-04-14T10:23:21Z","timestamp":1302776601000},"page":"1000-1021","source":"Crossref","is-referenced-by-count":20,"title":["Tighter Approximation Bounds for Minimum CDS in Unit Disk Graphs"],"prefix":"10.1007","volume":"61","author":[{"given":"Minming","family":"Li","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Peng-Jun","family":"Wan","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Frances","family":"Yao","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2011,4,15]]},"reference":[{"key":"9512_CR1","doi-asserted-by":"crossref","first-page":"157","DOI":"10.1145\/513800.513820","volume-title":"Proceedings of the 3rd ACM International Symposium on Mobile Ad Hoc Networking and Computing (MOBIHOC02)","author":"K.M. Alzoubi","year":"2002","unstructured":"Alzoubi, K.M., Wan, P.-J., Frieder, O.: Message-optimal connected dominating sets in mobile ad hoc networks. In: Proceedings of the 3rd ACM International Symposium on Mobile Ad Hoc Networking and Computing (MOBIHOC02), pp.\u00a0157\u2013164 (2002)"},{"key":"9512_CR2","first-page":"376","volume-title":"Proceedings of the IEEE International Conference on Communications (ICC97)","author":"V. Bharghavan","year":"1997","unstructured":"Bharghavan, V., Das, B.: Routing in ad hoc networks using minimum connected dominating sets. In: Proceedings of the IEEE International Conference on Communications (ICC97), pp.\u00a0376\u2013380 (1997)"},{"key":"9512_CR3","first-page":"329","volume-title":"Handbook of Combinatorial Optimization","author":"J. Blum","year":"2004","unstructured":"Blum, J., Ding, M., 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, Dordrecht (2004)"},{"key":"9512_CR4","first-page":"251","volume-title":"Proceedings of the 6th Joint Conference on Information Science (JCIS02)","author":"M. Cadei","year":"2002","unstructured":"Cadei, M., Cheng, X., Du, D.-Z.: Connected domination in ad hoc wireless networks. In: Proceedings of the 6th Joint Conference on Information Science (JCIS02), pp.\u00a0251\u2013255 (2002)"},{"issue":"3","key":"9512_CR5","doi-asserted-by":"crossref","first-page":"233","DOI":"10.1287\/moor.4.3.233","volume":"4","author":"V. Chv\u00e1tal","year":"1979","unstructured":"Chv\u00e1tal, V.: A greedy heuristic for the set-covering problem. Math. Oper. Res. 4(3), 233\u2013235 (1979)","journal-title":"Math. Oper. Res."},{"issue":"3","key":"9512_CR6","doi-asserted-by":"crossref","first-page":"444","DOI":"10.1145\/1167935.1167941","volume":"2","author":"S. Funke","year":"2006","unstructured":"Funke, S., Kesselman, A., Meyer, U., Segal, M.: A simple improved distributed algorithm for minimum CDS in unit disk graphs. ACM Trans. Sens. Netw. 2(3), 444\u2013453 (2006)","journal-title":"ACM Trans. Sens. Netw."},{"issue":"8","key":"9512_CR7","doi-asserted-by":"crossref","first-page":"927","DOI":"10.1002\/wcm.356","volume":"5","author":"Y.S. Li","year":"2005","unstructured":"Li, Y.S., Thai, M.T., Wang, F., Yi, C.-W., Wan, P.-J., Du, D.-Z.: On greedy construction of connected dominating sets in wireless networks. Wirel. Commun. Mob. Comput. 5(8), 927\u2013932 (2005)","journal-title":"Wirel. Commun. Mob. Comput."},{"key":"9512_CR8","volume-title":"Geometric Measure Theory: An Introduction","author":"F. Lin","year":"2003","unstructured":"Lin, F., Yang, X.: Geometric Measure Theory: An Introduction. International Press, Somerville (2003)"},{"issue":"1","key":"9512_CR9","doi-asserted-by":"crossref","first-page":"14","DOI":"10.1109\/71.980024","volume":"13","author":"I. Stojmenovic","year":"2002","unstructured":"Stojmenovic, I., Seddigh, M., Zunic, J.: Dominating sets and neighbor elimination based broadcasting algorithms in wireless networks. IEEE Trans. Parallel Distrib. Syst. 13(1), 14\u201325 (2002)","journal-title":"IEEE Trans. Parallel Distrib. Syst."},{"issue":"2","key":"9512_CR10","doi-asserted-by":"crossref","first-page":"141","DOI":"10.1023\/B:MONE.0000013625.87793.13","volume":"9","author":"P.-J. Wan","year":"2004","unstructured":"Wan, P.-J., Alzoubi, K.M., Frieder, O.: Distributed construction of connected dominating set in wireless ad hoc networks. Mob. Netw. Appl. 9(2), 141\u2013149 (2004)","journal-title":"Mob. Netw. Appl."},{"key":"9512_CR11","doi-asserted-by":"crossref","first-page":"337","DOI":"10.1109\/ICDCS.2008.15","volume-title":"Proceedings of the 28th International Conference on Distributed Computing Systems","author":"P.-J. Wan","year":"2008","unstructured":"Wan, P.-J., Wang, L., Yao, F.: Two-phased approximation algorithms for minimum CDS in wireless ad hoc networks. In: Proceedings of the 28th International Conference on Distributed Computing Systems, pp.\u00a0337\u2013344 (2008)"},{"issue":"1\u20133","key":"9512_CR12","doi-asserted-by":"crossref","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, S.C.-H.: Minimum connected dominating sets and maximal independent sets in unit disk graphs. Theor. Comput. Sci. 352(1\u20133), 1\u20137 (2006)","journal-title":"Theor. Comput. Sci."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-011-9512-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-011-9512-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-011-9512-7","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,29]],"date-time":"2019-05-29T09:45:07Z","timestamp":1559123107000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-011-9512-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,4,15]]},"references-count":12,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2011,12]]}},"alternative-id":["9512"],"URL":"https:\/\/doi.org\/10.1007\/s00453-011-9512-7","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2011,4,15]]}}}