{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,13]],"date-time":"2026-05-13T09:07:17Z","timestamp":1778663237423,"version":"3.51.4"},"reference-count":23,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2010,6,9]],"date-time":"2010-06-09T00:00:00Z","timestamp":1276041600000},"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":[[2011,5]]},"DOI":"10.1007\/s11590-010-0208-8","type":"journal-article","created":{"date-parts":[[2010,6,8]],"date-time":"2010-06-08T06:48:32Z","timestamp":1275979712000},"page":"297-306","source":"Crossref","is-referenced-by-count":23,"title":["An exact algorithm for minimum CDS with shortest path constraint in wireless networks"],"prefix":"10.1007","volume":"5","author":[{"given":"Ling","family":"Ding","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Xiaofeng","family":"Gao","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Weili","family":"Wu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Wonjun","family":"Lee","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Xu","family":"Zhu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ding-Zhu","family":"Du","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2010,6,9]]},"reference":[{"key":"208_CR1","first-page":"14","volume":"1","author":"Y.-P. Tsai","year":"2009","unstructured":"Tsai Y.-P., Hsu T.-L., Liu R.-S., Ho Y.-K.: A backbone routing protocol based on the connected dominating set in ad hoc networks. World Cong. Comput. Sci. Inf. Eng. 1, 14\u201318 (2009)","journal-title":"World Cong. Comput. Sci. Inf. Eng."},{"issue":"2","key":"208_CR2","doi-asserted-by":"crossref","first-page":"183","DOI":"10.1002\/wcm.378","volume":"6","author":"X. Cheng","year":"2006","unstructured":"Cheng X., Ding M., Du D.H., Jia X.: Virtual backbone construction in multihop ad hoc wireless networks: Research articles. Wireless Commun. Mobile Comput. 6(2), 183\u2013190 (2006)","journal-title":"Wireless Commun. Mobile Comput."},{"key":"208_CR3","unstructured":"Yiwei, W., Chunyu, A., Shan, G., Yingshu, L.: p-Percent coverage in wireless sensor networks. In: WASA \u201908: Proceedings of the third international conference on wireless algorithms, systems, and applications, pp. 200\u2013211. Springer, Berlin (2008)"},{"key":"208_CR4","doi-asserted-by":"crossref","first-page":"839","DOI":"10.1109\/ICCEE.2008.140","volume":"0","author":"A. Iqbal","year":"2008","unstructured":"Iqbal A., Ahmed N., Mostofa Akbar M.: Directional antenna based connected dominating set construction for energy efficient broadcasting in wireless ad hoc network. Int. Conf. Comput. Electr. Eng. 0, 839\u2013843 (2008)","journal-title":"Int. Conf. Comput. Electr. Eng."},{"issue":"1","key":"208_CR5","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), 1\u20137 (2006)","journal-title":"Theor. Comput. Sci."},{"key":"208_CR6","doi-asserted-by":"crossref","first-page":"59","DOI":"10.1109\/JCN.2002.6596934","volume":"4","author":"J. Wu","year":"2002","unstructured":"Wu J., Dai F., Gao M., Stojmenovic I.: On calculating power-aware connected dominating sets for efficient routing in ad hoc wireless networks. IEEE\/KICS J. Commun. Netw. 4, 59\u201370 (2002)","journal-title":"IEEE\/KICS J. Commun. Netw."},{"key":"208_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 minimum connected dominating set in ad hoc wireless networks. Networks 42, 202\u2013208 (2003)","journal-title":"Networks"},{"key":"208_CR8","doi-asserted-by":"crossref","unstructured":"Mohammed, K., Gewali, L., Muthukumar, V.: Generating quality dominating sets for sensor network. In: ICCIMA \u201905: Proceedings of the sixth international conference on computational intelligence and multimedia applications, pp. 204\u2013211. IEEE Computer Society, Washington, DC (2005)","DOI":"10.1109\/ICCIMA.2005.33"},{"key":"208_CR9","doi-asserted-by":"crossref","unstructured":"Zhang, N., Shin, I., Zou, F., Wu, W., Thai, M.T.: Trade-off scheme for fault tolerant connected dominating sets on size and diameter. In: FOWANC \u201908: Proceeding of the 1st ACM international workshop on foundations of wireless ad hoc and sensor networking and computing, pp. 1\u20138. ACM, New York (2008)","DOI":"10.1145\/1374718.1374720"},{"issue":"2","key":"208_CR10","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. 20(2), 147\u2013157 (2009)","journal-title":"IEEE Trans. Parallel Distrib. Syst."},{"key":"208_CR11","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of np-Completeness. Series of Books in the Mathematical Sciences. W. H. Freeman, San Francisco (1979)"},{"issue":"1\u20133","key":"208_CR12","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. Discret. Math. 86(1\u20133), 165\u2013177 (1990)","journal-title":"Discret. Math."},{"key":"208_CR13","doi-asserted-by":"crossref","unstructured":"Du, D.-Z., Lu, B., Ngo, H., Pardalos, P.M.: Steiner tree problems. In: Floudas, C., Pardalos, P. (eds.) Encyclopedia of Optimization, vol. 5, pp. 227\u2013290. Kluwer (2001)","DOI":"10.1007\/0-306-48332-7_489"},{"issue":"4","key":"208_CR14","doi-asserted-by":"crossref","first-page":"374","DOI":"10.1007\/PL00009201","volume":"20","author":"S. Guha","year":"1996","unstructured":"Guha S., Khuller S.: Approximation algorithms for connected dominating sets. Algorithmica 20(4), 374\u2013387 (1996)","journal-title":"Algorithmica"},{"issue":"1\u20133","key":"208_CR15","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 sets. Theor. Comput. Sci. 329(1\u20133), 325\u2013330 (2004)","journal-title":"Theor. Comput. Sci."},{"issue":"1","key":"208_CR16","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. J. Glob. Optim. 35(1), 111\u2013119 (2006)","journal-title":"J. Glob. Optim."},{"issue":"1\u20133","key":"208_CR17","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.-D., Lin G.-H., Wang L., Xue G.: Approximations for steiner trees with minimum number of steiner points. J. Glob. Optim. 18(1\u20133), 17\u201333 (2000)","journal-title":"J. Glob. Optim."},{"key":"208_CR18","volume-title":"Handbook of Combinatorial Optimization","author":"D.-Z. Du","year":"2004","unstructured":"Du D.-Z., Pardalos P.: Handbook of Combinatorial Optimization. Kluwer, Dordrecht (2004)"},{"key":"208_CR19","unstructured":"Das, B., Bharghavan, V.: Routing in ad-hoc networks using minimum connected dominating sets. In: Proceedings of IEEE ICC (1997)"},{"key":"208_CR20","unstructured":"Butenko, S., Cheng, X.Z., Du, D.-Z., Pardalos, P.M.: On the construction of virtual backbone for ad hoc wireless network. In: Proceedings of conference on cooperative control and optimization (2001)"},{"key":"208_CR21","doi-asserted-by":"crossref","unstructured":"Alzoubi, K., Wan, P.-J., Frieder, O.: New distributed algorithm for connected dominating set in wireless ad hoc networks. In: Proceedings of IEEE HICSS (2002)","DOI":"10.1145\/513800.513820"},{"key":"208_CR22","doi-asserted-by":"crossref","unstructured":"Di, W., Yan, Q., Ning, T.: Connected dominating set based hybrid routing algorithm in ad hoc networks with obstacles. In: Proceedings of IEEE ICC (2006)","DOI":"10.1109\/ICC.2006.255708"},{"key":"208_CR23","unstructured":"Deb, B., Bhatnagar, S., Nath, B.: Multi-resolution state retrieval in sensor networks. In: Proceedings of IEEE international workshop on sensor network protocols and applications (2003)"}],"container-title":["Optimization Letters"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s11590-010-0208-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s11590-010-0208-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s11590-010-0208-8","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T19:14:50Z","timestamp":1740165290000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s11590-010-0208-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,6,9]]},"references-count":23,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2011,5]]}},"alternative-id":["208"],"URL":"https:\/\/doi.org\/10.1007\/s11590-010-0208-8","relation":{},"ISSN":["1862-4472","1862-4480"],"issn-type":[{"value":"1862-4472","type":"print"},{"value":"1862-4480","type":"electronic"}],"subject":[],"published":{"date-parts":[[2010,6,9]]}}}