{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,25]],"date-time":"2026-07-25T16:03:29Z","timestamp":1784995409411,"version":"3.55.0"},"reference-count":21,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2013,6,12]],"date-time":"2013-06-12T00:00:00Z","timestamp":1370995200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J Comb Optim"],"published-print":{"date-parts":[[2014,7]]},"DOI":"10.1007\/s10878-013-9638-4","type":"journal-article","created":{"date-parts":[[2013,6,11]],"date-time":"2013-06-11T04:01:21Z","timestamp":1370923281000},"page":"310-319","source":"Crossref","is-referenced-by-count":34,"title":["A greedy algorithm for the fault-tolerant connected dominating set in a general graph"],"prefix":"10.1007","volume":"28","author":[{"given":"Jiao","family":"Zhou","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Zhao","family":"Zhang","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Weili","family":"Wu","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Kai","family":"Xing","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2013,6,12]]},"reference":[{"key":"9638_CR1","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 (2003) A polynomial-time approximation scheme for minimum connected dominating set in ad hoc wireless networks. Networks 42:202\u2013208","journal-title":"Networks"},{"issue":"7","key":"9638_CR2","doi-asserted-by":"crossref","first-page":"947","DOI":"10.1016\/j.jpdc.2005.12.010","volume":"66","author":"F Dai","year":"2006","unstructured":"Dai F, Wu J (2006) On constructing $$k$$ k -connected $$k$$ k -dominating set in wireless ad hoc and sensor networks. J Parallel Distrib Comput 66(7):947\u2013958","journal-title":"J Parallel Distrib Comput"},{"key":"9638_CR3","unstructured":"Du DZ, Graham RL, Pardalos PM, Wan PJ, Wu WL, Zhao W. (2008) Analysis of greedy approximation with nonsubmodular potential functions. In: Proceedings 19th ACMSIAM symposium on discrete algorithms, pp 167\u2013175"},{"key":"9638_CR4","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4614-1701-9","volume-title":"Design and analysis of approximation algorithms","author":"D Du","year":"2012","unstructured":"Du D, Ko K, Hu X (2012) Design and analysis of approximation algorithms. Springer, New York"},{"key":"9638_CR5","doi-asserted-by":"crossref","first-page":"56","DOI":"10.1109\/PROC.1987.13705","volume":"75","author":"A Ephremides","year":"1987","unstructured":"Ephremides A, Wieselthier J, Baker D (1987) A design concept for reliable mobile radio networks with frequency hopping signaling. Proc IEEE 75:56\u201373","journal-title":"Proc IEEE"},{"issue":"1","key":"9638_CR6","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 (2009) Analysis on theoretical bounds for approximating dominating set problems. Discret Math Algorithms Appl 1(1):71\u201384","journal-title":"Discret Math Algorithms Appl"},{"issue":"4","key":"9638_CR7","doi-asserted-by":"crossref","first-page":"374","DOI":"10.1007\/PL00009201","volume":"20","author":"S Guha","year":"1998","unstructured":"Guha S, Khuller S (1998) Approximation algorithms for connected dominating sets. Algorithmica 20(4):374\u2013387","journal-title":"Algorithmica"},{"key":"9638_CR8","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 (2009) Minimum connected $$r$$ r -hop $$k$$ k -dominating set in wireless networks. Discret Math Algorithms Appl 1:45\u201358","journal-title":"Discret Math Algorithms Appl"},{"key":"9638_CR9","first-page":"699","volume":"5878","author":"M Li","year":"2009","unstructured":"Li M, Wan P, Yao F (2009) Tighter approximation bounds for minimum CDS in wireless ad hoc networks. ISAAC\u20192009 LNCS 5878:699\u2013709","journal-title":"ISAAC\u20192009 LNCS"},{"key":"9638_CR10","doi-asserted-by":"crossref","first-page":"118","DOI":"10.1007\/s10878-010-9346-2","volume":"23","author":"Y Li","year":"2012","unstructured":"Li Y, Wu Y, Ai C, Beyah R (2012) On the construction of $$k$$ k -connected $$m$$ m -dominating sets in wireless networks. J Comb Optim 23:118\u2013139","journal-title":"J Comb Optim"},{"issue":"1","key":"9638_CR11","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 (2004) A greedy approximation for minimum connected dominating sets. Theor Comput Sci 329(1):325\u2013330","journal-title":"Theor Comput Sci"},{"key":"9638_CR12","doi-asserted-by":"crossref","first-page":"99","DOI":"10.1007\/s10878-007-9124-y","volume":"16","author":"W Shang","year":"2008","unstructured":"Shang W, Yao F, Wan P, Hu X (2008) On minimum $$m$$ m -connected $$k$$ k -dominating set problem in unit disc graphs. J Comb Optim 16:99\u2013106","journal-title":"J Comb Optim"},{"key":"9638_CR13","doi-asserted-by":"crossref","first-page":"49","DOI":"10.1016\/j.tcs.2007.05.025","volume":"385","author":"M Thai","year":"2007","unstructured":"Thai M, Zhang N, Tiwari R, Xu X (2007) On approximation algorithms of $$k$$ k -connected $$m$$ m -dominating sets in disk graphs. Theor Comput Sci 385:49\u201359","journal-title":"Theor Comput Sci"},{"issue":"2","key":"9638_CR14","doi-asserted-by":"crossref","first-page":"141","DOI":"10.1023\/B:MONE.0000013625.87793.13","volume":"9","author":"P Wan","year":"2004","unstructured":"Wan P, Alzoubi K, Frieder O (2004) Distributed construction of connected dominating set in wireless ad hoc networks. ACM\/Springer Mob Netw Appl 9(2):141\u2013149","journal-title":"ACM\/Springer Mob Netw Appl"},{"key":"9638_CR15","doi-asserted-by":"crossref","unstructured":"Wan P, Wang L, Yao F. (2008) Two-phased approximation algorithms for minimum CDS in wireless ad hoc networks. In: IEEE ICDCS, pp 337\u2013344","DOI":"10.1109\/ICDCS.2008.15"},{"issue":"3","key":"9638_CR16","doi-asserted-by":"crossref","first-page":"1230","DOI":"10.1109\/TWC.2009.051053","volume":"8","author":"F Wang","year":"2009","unstructured":"Wang F, Thai M, Du D (2009) On the construction of 2-connected virtual backbone in wireless networks. IEEE Trans Wirel Commun 8(3):1230\u20131237","journal-title":"IEEE Trans Wirel Commun"},{"key":"9638_CR17","doi-asserted-by":"crossref","unstructured":"Wang W, Kim D, An M, Gao W, Li X, Zhang Z, Wu W (2012) On construction of quality fault-tolerant virtual backbone in wireless networks. IEEE\/ACM Trans Netw. doi: 10.1109\/TNET.2012.2227791","DOI":"10.1109\/TNET.2012.2227791"},{"issue":"1\u20133","key":"9638_CR18","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 (2006) Minimum connected dominating sets and maximal independent sets in unit disk graphs. Theor Comput Sci 352(1\u20133):1\u20137","journal-title":"Theor Comput Sci"},{"key":"9638_CR19","doi-asserted-by":"crossref","unstructured":"Wu Y, Wang F, Thai M, Li Y (2007) Constructing $$k$$ k -connected $$m$$ m -dominating sets in wireless sensor networks. In: Military communications conference, pp 1\u20137","DOI":"10.1109\/MILCOM.2007.4454774"},{"key":"9638_CR20","doi-asserted-by":"crossref","first-page":"451","DOI":"10.1007\/s10898-008-9384-9","volume":"45","author":"Z Zhang","year":"2009","unstructured":"Zhang Z, Gao XF, Wu WL, Du DZ (2009) A PTAS for minimum connected dominating set in 3-dimensional wireless sensor networks. J Glob Optim 45:451\u2013458","journal-title":"J Glob Optim"},{"issue":"4","key":"9638_CR21","doi-asserted-by":"crossref","first-page":"485","DOI":"10.1142\/S1793830909000361","volume":"1","author":"Z Zhang","year":"2009","unstructured":"Zhang Z, Liu Q, Li D (2009) Two algorithms for connected $$r$$ r -hop $$k$$ k -dominationg set. Discret Math Algorithms Appl 1(4):485\u2013498","journal-title":"Discret Math Algorithms Appl"}],"container-title":["Journal of Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-013-9638-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10878-013-9638-4\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-013-9638-4","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,7,15]],"date-time":"2019-07-15T03:39:21Z","timestamp":1563161961000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10878-013-9638-4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,6,12]]},"references-count":21,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2014,7]]}},"alternative-id":["9638"],"URL":"https:\/\/doi.org\/10.1007\/s10878-013-9638-4","relation":{},"ISSN":["1382-6905","1573-2886"],"issn-type":[{"value":"1382-6905","type":"print"},{"value":"1573-2886","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013,6,12]]}}}