{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,6]],"date-time":"2026-01-06T13:36:43Z","timestamp":1767706603851},"reference-count":31,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2014,2,25]],"date-time":"2014-02-25T00:00:00Z","timestamp":1393286400000},"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":[[2016,1]]},"DOI":"10.1007\/s10878-014-9720-6","type":"journal-article","created":{"date-parts":[[2014,2,24]],"date-time":"2014-02-24T06:35:47Z","timestamp":1393223747000},"page":"136-151","source":"Crossref","is-referenced-by-count":34,"title":["A greedy algorithm for the minimum $$2$$ 2 -connected $$m$$ m -fold dominating set problem"],"prefix":"10.1007","volume":"31","author":[{"given":"Yishuo","family":"Shi","sequence":"first","affiliation":[]},{"given":"Yaping","family":"Zhang","sequence":"additional","affiliation":[]},{"given":"Zhao","family":"Zhang","sequence":"additional","affiliation":[]},{"given":"Weili","family":"Wu","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2014,2,25]]},"reference":[{"key":"9720_CR1","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-84628-970-5","volume-title":"Graph theory","author":"JA Bondy","year":"2008","unstructured":"Bondy JA, Murty USR (2008) Graph theory. Springer, New York"},{"key":"9720_CR2","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 (2003) A polynomial-time approximation scheme for minimum connected dominating set in ad hoc wireless networks. Networks 42:202\u2013208","journal-title":"Networks"},{"key":"9720_CR3","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:947\u2013958","journal-title":"J Parallel Distrib Comput"},{"key":"9720_CR4","doi-asserted-by":"crossref","unstructured":"Das B, Bharghavan V (1997) Routing in ad hoc networks using minimum connected dominating sets. In: ICC\u201997, Montreal, Canada, pp 376\u2013380.","DOI":"10.1109\/ICC.1997.605303"},{"key":"9720_CR5","unstructured":"Du D.-Z, Graham R.L, Pardalos P.M, Wan P.-J, Wu W, Zhao W (2008) Analysis of greedy approximation with nonsubmodular potential functions. In: Proceedings of the 19th ACMSIAM Symposium on Discrete Algorithms, pp 167\u2013175."},{"key":"9720_CR6","volume-title":"Design and analysis of approximation algorithms","author":"D-Z Du","year":"2012","unstructured":"Du D-Z, Ko K-I, Hu X (2012) Design and analysis of approximation algorithms. Springer, New York"},{"key":"9720_CR7","volume-title":"Connected dominating set: theory and applications","author":"D-Z Du","year":"2012","unstructured":"Du D-Z, Wan P-J (2012) Connected dominating set: theory and applications. Springer, New York"},{"key":"9720_CR8","doi-asserted-by":"crossref","first-page":"56","DOI":"10.1109\/PROC.1987.13705","volume":"759","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 759:56\u201373","journal-title":"Proc IEEE"},{"key":"9720_CR9","doi-asserted-by":"crossref","first-page":"838","DOI":"10.1016\/j.jcss.2005.05.006","volume":"72","author":"L Fleischer","year":"2006","unstructured":"Fleischer L, Jain K, Williamson DP (2006) Iterative rounding 2-approximation algorithms for minimum-cost vertex connectivity problems. J Comput Syst Sci 72:838\u2013867","journal-title":"J Comput Syst Sci"},{"key":"9720_CR10","volume-title":"Computers and intractability: a guide to the theory of NP-completeness","author":"MR Garey","year":"1979","unstructured":"Garey MR, Johnson DS (1979) Computers and intractability: a guide to the theory of NP-completeness. Freeman, New York"},{"key":"9720_CR11","doi-asserted-by":"crossref","first-page":"235","DOI":"10.1007\/978-1-4613-0255-1_7","volume-title":"Steiner trees in industries","author":"C Gropl","year":"2001","unstructured":"Gropl C, Hougardy S, Nierhoff T, Promel HJ (2001) Approximation algorithms for the Steiner tree problem in graphs. In: Du D-Z, Cheng X (eds) Steiner trees in industries. Kluwer, Dordrecht, pp 235\u2013279"},{"key":"9720_CR12","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:374\u2013387","journal-title":"Algorithmica"},{"key":"9720_CR13","doi-asserted-by":"crossref","first-page":"57","DOI":"10.1006\/inco.1998.2754","volume":"150","author":"S Guha","year":"1999","unstructured":"Guha S, Khuller S (1999) Improved methods for approximating node weighted Steiner trees and connected dominating sets. Inf Comput 150:57\u201374","journal-title":"Inf Comput"},{"key":"9720_CR14","unstructured":"Kim D, Wang W, Li X, Zhang Z (2010)Wu W. A new constant factor approximation for computing $$3$$ 3 -connected $$m$$ m -dominating sets in homogeneous wireless networks. In: IEEE INFOCOM, pp 1\u20139."},{"key":"9720_CR15","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. Discrete Math Algorithms Appl 1:45\u201358","journal-title":"Discrete Math Algorithms Appl"},{"key":"9720_CR16","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"},{"key":"9720_CR17","doi-asserted-by":"crossref","first-page":"434","DOI":"10.1109\/TNET.2009.2033273","volume":"18","author":"S Misra","year":"2010","unstructured":"Misra S, Hong S, Xue G, Tang J (2010) Constrained realy node placement in wireless sensor networks: formulation and approximations. IEEE\/ACM Trans Netw 18:434\u2013447","journal-title":"IEEE\/ACM Trans Netw"},{"key":"9720_CR18","doi-asserted-by":"crossref","first-page":"3001","DOI":"10.1137\/080729645","volume":"39","author":"Z Nutov","year":"2010","unstructured":"Nutov Z (2010) Approximating Steiner networks with node-weights. SIAM J Comput 39:3001\u20133022","journal-title":"SIAM J Comput"},{"key":"9720_CR19","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:325\u2013330","journal-title":"Theor Comput Sci"},{"key":"9720_CR20","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-J, 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":"9720_CR21","doi-asserted-by":"crossref","first-page":"49","DOI":"10.1016\/j.tcs.2007.05.025","volume":"385","author":"MT Thai","year":"2007","unstructured":"Thai MT, 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"},{"key":"9720_CR22","volume-title":"Approximation algorithms","author":"VV Vazirani","year":"2001","unstructured":"Vazirani VV (2001) Approximation algorithms. Springer, New York"},{"key":"9720_CR23","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 KM, Frieder O (2004) Distributed construction of connected dominating set in wireless ad hoc networks. ACM\/Springer Mob Netw Appl 9:141\u2013149","journal-title":"ACM\/Springer Mob Netw Appl"},{"key":"9720_CR24","doi-asserted-by":"crossref","first-page":"1230","DOI":"10.1109\/TWC.2009.051053","volume":"8","author":"F Wang","year":"2009","unstructured":"Wang F, Thai MT, Du D-Z (2009) On the construction of 2-connected virtual backbone in wireless networks. IEEE Trans Wirel Commun 8:1230\u20131237","journal-title":"IEEE Trans Wirel Commun"},{"key":"9720_CR25","doi-asserted-by":"crossref","unstructured":"Wang W, Kim D, An M, Gao W, Li X, Zhang, 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"},{"key":"9720_CR26","doi-asserted-by":"crossref","unstructured":"Wu Y, Wang F, Thai M.T, Li Y.(2007) Constructing $$k$$ k -connected $$m$$ m -dominating sets in wireless sensor networks. In: Military communications conference, Orlando, FL","DOI":"10.1109\/MILCOM.2007.4454774"},{"key":"9720_CR27","doi-asserted-by":"crossref","first-page":"1399","DOI":"10.1109\/TMC.2011.126","volume":"11","author":"D Yang","year":"2012","unstructured":"Yang D, Misra S, Fang X, Xue G, Zhang J (2012) Two-tiered constrained relay node placement in wireless sensor networks: computational complexity and efficient approximations. IEEE Trans Mob Comput 11:1399\u20131411","journal-title":"IEEE Trans Mob Comput"},{"key":"9720_CR28","unstructured":"Zelikovsky A (1996) Better approximation bounds for the network and euclidean Steiner tree problems. Technical report CS-96-06, Department of Computer Science, University of Vir- ginia, Charlottesville"},{"key":"9720_CR29","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 X, Wu W, Du D-Z (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"},{"key":"9720_CR30","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. Discrete Math Algorithms Appl 1:485\u2013498","journal-title":"Discrete Math Algorithms Appl"},{"key":"9720_CR31","doi-asserted-by":"crossref","unstructured":"Zhou J, Zhang Z, Wu W, Xing X. A Greedy algorithm for the fault-tolerant connected dominating set in a general graph. J. Combinatorial, Optimization. doi: 10.1007\/s10878-013-9638-4 .","DOI":"10.1007\/s10878-013-9638-4"}],"container-title":["Journal of Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-014-9720-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10878-014-9720-6\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-014-9720-6","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,7]],"date-time":"2019-08-07T22:22:25Z","timestamp":1565216545000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10878-014-9720-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,2,25]]},"references-count":31,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2016,1]]}},"alternative-id":["9720"],"URL":"https:\/\/doi.org\/10.1007\/s10878-014-9720-6","relation":{},"ISSN":["1382-6905","1573-2886"],"issn-type":[{"value":"1382-6905","type":"print"},{"value":"1573-2886","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014,2,25]]}}}