{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,2]],"date-time":"2025-11-02T16:29:12Z","timestamp":1762100952150},"reference-count":49,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2009,10,23]],"date-time":"2009-10-23T00:00:00Z","timestamp":1256256000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Optim Lett"],"published-print":{"date-parts":[[2010,8]]},"DOI":"10.1007\/s11590-009-0151-8","type":"journal-article","created":{"date-parts":[[2009,10,22]],"date-time":"2009-10-22T07:24:24Z","timestamp":1256196264000},"page":"347-358","source":"Crossref","is-referenced-by-count":21,"title":["Wireless networking, dominating and packing"],"prefix":"10.1007","volume":"4","author":[{"given":"Weili","family":"Wu","sequence":"first","affiliation":[]},{"given":"Xiaofeng","family":"Gao","sequence":"additional","affiliation":[]},{"given":"Panos M.","family":"Pardalos","sequence":"additional","affiliation":[]},{"given":"Ding-Zhu","family":"Du","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2009,10,23]]},"reference":[{"key":"151_CR1","doi-asserted-by":"crossref","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, Lausanne, Switzerland, 9\u201311 June 2002","DOI":"10.1145\/513800.513820"},{"key":"151_CR2","doi-asserted-by":"crossref","unstructured":"Ambuehl, C., Erlebach, T., Mihalak, M., Nunkesser M.: Constant-factor approximation for minimum-weight (connected) dominating sets in unit disk graphs. In: Proceedings of the 9th Workshop on Approximation Algorithms for Combinatorial Optimization Problems, LNCS 4110, pp. 3\u201314. Springer (2006)","DOI":"10.1007\/11830924_3"},{"key":"151_CR3","unstructured":"Bharghavan, V., Das, B.: Routing in ad hoc networks using minimum connected dominating sets. In: International Conference on Communication, Montreal, Canada, June 1997"},{"key":"151_CR4","unstructured":"Butenko, S., Ursulenko, O.: On minimum connected dominating set problem in unit-ball graphs. Preprint"},{"key":"151_CR5","unstructured":"Cadei, M., Cheng, M.X., Cheng, X., Du, D.-Z.: Connected domination in ad hoc wireless networks. In: Proceedings of the Sixth International Conference on Computer Science and Informatics (CS&I\u20192002) (2002)"},{"key":"151_CR6","doi-asserted-by":"crossref","first-page":"1671","DOI":"10.1137\/S0097539792238431","volume":"27","author":"M.-S. Chang","year":"1998","unstructured":"Chang M.-S.: Efficient algorithms for the domination problems on interval and circular-arc graphs. SIAM J. Comput. 27, 1671\u20131694 (1998)","journal-title":"SIAM J. Comput."},{"key":"151_CR7","doi-asserted-by":"crossref","first-page":"17","DOI":"10.1023\/A:1008384012064","volume":"18","author":"D. Chen","year":"2000","unstructured":"Chen D., Du D.-Z., Hu X., Lin G.-H., Wang L., Xue G.: Approximations for Steiner trees with minimum number of Steiner points. J. Glob. Optim. 18, 17\u201333 (2000)","journal-title":"J. Glob. Optim."},{"key":"151_CR8","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 Third ACM International Symposium on Mobile Ad Hoc Networking and Computing, Lausanne, Switzerland, 9\u201311 June 2002","DOI":"10.1145\/513800.513821"},{"key":"151_CR9","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 minimum connected dominating set in ad hoc wireless networks. Networks 42, 202\u2013208 (2003)","journal-title":"Networks"},{"key":"151_CR10","doi-asserted-by":"crossref","first-page":"165","DOI":"10.1016\/0012-365X(90)90358-O","volume":"86","author":"B.N. Clark","year":"1990","unstructured":"Clark B.N., Colbourn C.J., Johnson D.S.: Unit disk graphs. Discrete Math. 86, 165\u2013177 (1990)","journal-title":"Discrete Math."},{"key":"151_CR11","doi-asserted-by":"crossref","unstructured":"Clark, W.E., Dunning, L.A.: Tight upper bounds for the domination numbers of graphs with given order and minimum degree. Electron. J. Comb. 4(1) (1997). Research paper R 26, 25\u00a0pp","DOI":"10.37236\/1311"},{"key":"151_CR12","doi-asserted-by":"crossref","first-page":"756","DOI":"10.1016\/j.tcs.2008.11.015","volume":"410","author":"D. Dai","year":"2009","unstructured":"Dai D., Yu C.: A (5\u00a0+\u00a0\u03b5)-approximation algorithm for minimum weighted dominating set in unit disk graph. Theor. Comput. Sci. 410, 756\u2013765 (2009)","journal-title":"Theor. Comput. Sci."},{"key":"151_CR13","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 Dicrete Algorithms (SODA), pp. 167\u2013175, San Francisco, USA, 20\u201322 January 2008"},{"key":"151_CR14","doi-asserted-by":"crossref","unstructured":"Du, D.-Z., Wang, L., Xu, B.: The Euclidean bottleneck Steiner tree and Steiner tree with minimum number of Steiner Points. COCOON\u20192001, pp. 509\u2013518","DOI":"10.1007\/3-540-44679-6_57"},{"key":"151_CR15","doi-asserted-by":"crossref","unstructured":"Eriksson, H.: MBone: the multicast backbone. In: Communications of the ACM. August 1994","DOI":"10.1145\/179606.179627"},{"key":"151_CR16","doi-asserted-by":"crossref","unstructured":"Feige, U.: A threshold of ln n for approximating set-cover. In: Proceedings of the 28th ACM Symposium on Theory of Computing, pp. 314\u2013318 (1996)","DOI":"10.1145\/237814.237977"},{"key":"151_CR17","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.: A simple improved distributed algorithm for minimum CDS in unit disk graphs. ACM Trans. Sensor Netw. 2, 444\u2013453 (2006)","journal-title":"ACM Trans. Sensor Netw."},{"key":"151_CR18","doi-asserted-by":"crossref","first-page":"153","DOI":"10.1007\/s11276-006-3724-9","volume":"13","author":"S. Funke","year":"2007","unstructured":"Funke S., Kesselman A., Kuhn F., Lotker Z., Sega M.: Improved approximation algorithms for connected sensor cover. Wireless Netw. 13, 153\u2013164 (2007)","journal-title":"Wireless Netw."},{"issue":"1","key":"151_CR19","doi-asserted-by":"crossref","first-page":"71","DOI":"10.1142\/S1793830909000105","volume":"1","author":"X. Gao","year":"2009","unstructured":"Gao X., Wang Y., Li X., Wu W.: Analysis on theoretical bonds for approximating dominating set problems. Discrete Math. Algorithms Appl. 1(1), 71\u201384 (2009)","journal-title":"Discrete Math. Algorithms Appl."},{"key":"151_CR20","doi-asserted-by":"crossref","unstructured":"Gao, X., Huang, Y., Zhang, Z., Wu, W.: (6\u00a0+\u00a0\u03b5)-Approximation for minimum weight dominating set in unit disk graphs. COCOON, pp. 551\u2013557 (2008)","DOI":"10.1007\/978-3-540-69733-6_54"},{"key":"151_CR21","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. W. H. Freeman & Co., New York (1979)"},{"key":"151_CR22","doi-asserted-by":"crossref","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"},{"issue":"2","key":"151_CR23","doi-asserted-by":"crossref","first-page":"147","DOI":"10.1109\/TPDS.2008.74","volume":"20","author":"D. Kim","year":"2009","unstructured":"Kim D., Wu Y., Li Y., Zou F., Du D.-Z.: Constructing minimum connected dominating sets with bounded diameters in wireless networks. IEEE Trans. Parallel Distrib. Syst. (TPDS) 20(2), 147\u2013157 (2009)","journal-title":"IEEE Trans. Parallel Distrib. Syst. (TPDS)"},{"issue":"1","key":"151_CR24","doi-asserted-by":"crossref","first-page":"45","DOI":"10.1142\/S1793830909000087","volume":"1","author":"D. Li","year":"2009","unstructured":"Li D., Liu L., Yang H.: Minimum connected r-hop k-dominating set in wireless networks. Discrete Math. Algorithms Appl. 1(1), 45\u201357 (2009)","journal-title":"Discrete Math. Algorithms Appl."},{"key":"151_CR25","doi-asserted-by":"crossref","unstructured":"Li, M., Wan, P.-J., Yao, F.F.: Tighter approximation bounds for minimum CDS in wireless ad hoc networks. In: ISAAC\u20192009, pp. 677\u2013686 (2009)","DOI":"10.1007\/978-3-642-10631-6_71"},{"key":"151_CR26","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. Wiley J. Wireless Commun. Mobile Comput. 5, 927\u2013932 (2005)","journal-title":"Wiley J. Wireless Commun. Mobile Comput."},{"key":"151_CR27","doi-asserted-by":"crossref","first-page":"53","DOI":"10.1016\/S0020-0190(98)00201-4","volume":"69","author":"G.-H. Lin","year":"1999","unstructured":"Lin G.-H., Xue G.L.: Steiner tree problem with minimum number of Steiner points and bounded edge-length. Inf. Process. Lett. 69, 53\u201357 (1999)","journal-title":"Inf. Process. Lett."},{"key":"151_CR28","doi-asserted-by":"crossref","first-page":"111","DOI":"10.1007\/s10898-005-8466-1","volume":"35","author":"M. Min","year":"2006","unstructured":"Min M., Huang X., Huang C.-H., Wu W., Du H., Jia X.: Improving construction for connected dominating set with Steiner tree in wireless sensor networks. J. Glob. Optim. 35, 111\u2013119 (2006)","journal-title":"J. Glob. Optim."},{"key":"151_CR29","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/1383369.1383380","volume":"4","author":"T. Nieberg","year":"2008","unstructured":"Nieberg T., Hurink J., Kern W.: Approximation schemes for wireless networks. ACM Trans. Algorithms 4, 1\u201317 (2008)","journal-title":"ACM Trans. Algorithms"},{"key":"151_CR30","unstructured":"Robin, G., Zelikovsky, A.: Improved Steiner trees approximation in graphs. In: SIAM-ACM Symposium on Discrete Algorithms (SODA), pp. 770\u2013779, San Francisco, CA, January 2000"},{"key":"151_CR31","doi-asserted-by":"crossref","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 greedy approximation for minimum connected dominating set. Theor. Comput. Sci. 329, 325\u2013330 (2004)","journal-title":"Theor. Comput. Sci."},{"key":"151_CR32","doi-asserted-by":"crossref","unstructured":"Salhieh, A., Weinmann, J., Kochha, M., Schwiebert, L.: Power efficient topologies for wireless sensor networks. In: ICPP\u20192001, pp. 156\u2013163","DOI":"10.1109\/ICPP.2001.952059"},{"key":"151_CR33","first-page":"607","volume":"13","author":"E. Sampathkumar","year":"1979","unstructured":"Sampathkumar E., Walikar H.B.: The connected domination number of a graph. J. Math. Phys. Sci. 13, 607\u2013613 (1979)","journal-title":"J. Math. Phys. Sci."},{"key":"151_CR34","unstructured":"Sivakumar, R., Das, B., Bharghavan, V.: An improved spine-based infrastructure for routing in ad hoc networks. In: IEEE Symposium on Computer and Communications, Athens, Greece, June 1998"},{"key":"151_CR35","doi-asserted-by":"crossref","first-page":"565","DOI":"10.3390\/a2010565","volume":"2","author":"A. Sorokin","year":"2009","unstructured":"Sorokin A., Boyko N., Boginski V., Uryasev S., Pardalos P.M.: Mathematical programming techniques for sensor networks. Algorithms 2, 565\u2013581 (2009)","journal-title":"Algorithms"},{"key":"151_CR36","doi-asserted-by":"crossref","unstructured":"Stojmenovic, I., Seddigh, M., Zunic, J.: Dominating sets and neighbor elimination based broadcasting algorithms in wireless networks. In: Proceedings of IEEE Hawaii International Conference on System Sciences, January 2001","DOI":"10.1109\/HICSS.2001.927199"},{"key":"151_CR37","doi-asserted-by":"crossref","unstructured":"Wan, P.-J., Alzoubi, K.M., Frieder, O.: Distributed construction of connected dominating set in wireless ad hoc networks. ACM\/Springer Mobile Netw. Appl. 9(2), 141\u2013149. A preliminary version of this paper appeared in IEEE INFOCOM 2002 (2004)","DOI":"10.1023\/B:MONE.0000013625.87793.13"},{"key":"151_CR38","doi-asserted-by":"crossref","unstructured":"Wan, P.-J., Wang, L., Yao, F.: Two-phased approximation algorithms for minimum CDS in wireless ad hoc networks. In: IEEE ICDCS, pp. 337\u2013344 (2008)","DOI":"10.1109\/ICDCS.2008.15"},{"issue":"2","key":"151_CR39","doi-asserted-by":"crossref","first-page":"161","DOI":"10.1007\/s11036-006-4469-5","volume":"11","author":"Y. Wang","year":"2006","unstructured":"Wang Y., Li X.Y.: Localized construction of bounded degree and planar spanner for wireless ad hoc networks. Mobile Netw. Appl. 11(2), 161\u2013175 (2006)","journal-title":"Mobile Netw. Appl."},{"key":"151_CR40","unstructured":"Wang, Z., Wang, W., Kim, JU., Shan, S., Thuraisingham, B., Wu, W.: PTAS for minimum weighted dominating set in sparse graphs. J. Glob. Optim. (submitted)"},{"key":"151_CR41","unstructured":"Willson, J., Gao, X., Qu, Z., Zhu,Y., Li, Y., Wu, W.: Efficient distributed algorithms for topology control problem with shortest path constraints. (submitted)"},{"key":"151_CR42","doi-asserted-by":"crossref","unstructured":"Wu, J., Li, H.: On calculating connected dominating set for efficient routing in ad hoc wireless networks. In: Proceedings of the 3rd ACM International Workshop on Discrete Algorithms and Methods for Mobile Computing and Communications, pp. 7\u201314 (1999)","DOI":"10.1145\/313239.313261"},{"key":"151_CR43","unstructured":"Wu, W., Du, H., Jia, X., Li, Y., Huang, C.-H., Du, D.-Z.: Minimum connected dominating sets and maximal independent sets in unit disk graphs. Networks (submitted)"},{"key":"151_CR44","doi-asserted-by":"crossref","first-page":"812","DOI":"10.1016\/j.tcs.2008.11.005","volume":"410","author":"Z. Zhang","year":"2009","unstructured":"Zhang Z., Gao X., Wu W.: Algorithms for connected set cover problem and fault-tolerant connected set cover problem. Theor. Comput. Sci 410, 812\u2013817 (2009)","journal-title":"Theor. Comput. Sci"},{"key":"151_CR45","doi-asserted-by":"crossref","unstructured":"Zhang, Z., Gao, X., Wu, W., Du, D.-Z.: A PTAS for minimum connected dominating set in 3-dimensional Wireless sensor networks. J. Glob. Optim. 45(3), (2009)","DOI":"10.1007\/s10898-008-9384-9"},{"key":"151_CR46","volume-title":"Shere Packings","author":"C. Zong","year":"1999","unstructured":"Zong C.: Shere Packings. Springer, New York (1999)"},{"key":"151_CR47","unstructured":"Zou, F., Wang, Y., Li, X., Xu, X., Du, H., Wan, P., Wu, W.: New approximations for minimum-weighted dominating set and minimum-weighted connected dominating set on unit disk graphs. Theor. Comput. Sci. (to appear)"},{"key":"151_CR48","unstructured":"Zou, F., Li, X., Kim, D., Wu, W.: A constant approximation algorithm for node-weighted Steiner tree in unit disk graphs. J. Comb. Optim. (to appear)"},{"key":"151_CR49","unstructured":"Zou, F., Li, X., Kim, D., Wu, W.: Minimum connected dominating set in 3-dimensional wireless network. Optim. Methods Softw. (to appear)"}],"container-title":["Optimization Letters"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s11590-009-0151-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s11590-009-0151-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s11590-009-0151-8","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,5,23]],"date-time":"2020-05-23T05:54:48Z","timestamp":1590213288000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s11590-009-0151-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,10,23]]},"references-count":49,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2010,8]]}},"alternative-id":["151"],"URL":"https:\/\/doi.org\/10.1007\/s11590-009-0151-8","relation":{},"ISSN":["1862-4472","1862-4480"],"issn-type":[{"value":"1862-4472","type":"print"},{"value":"1862-4480","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009,10,23]]}}}