{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,6]],"date-time":"2026-01-06T13:51:47Z","timestamp":1767707507698,"version":"3.37.3"},"reference-count":25,"publisher":"Springer Science and Business Media LLC","issue":"6","license":[{"start":{"date-parts":[[2022,2,16]],"date-time":"2022-02-16T00:00:00Z","timestamp":1644969600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2022,2,16]],"date-time":"2022-02-16T00:00:00Z","timestamp":1644969600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2022,6]]},"DOI":"10.1007\/s00453-022-00935-x","type":"journal-article","created":{"date-parts":[[2022,2,16]],"date-time":"2022-02-16T05:02:30Z","timestamp":1644987750000},"page":"1511-1525","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Approximating k-Connected m-Dominating Sets"],"prefix":"10.1007","volume":"84","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-6629-3243","authenticated-orcid":false,"given":"Zeev","family":"Nutov","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2022,2,16]]},"reference":[{"doi-asserted-by":"crossref","unstructured":"Amb\u00fchl, C., Erlebach, T., Mihal\u00e1k, M., Nunkesser, M.: Constant-factor approximation for minimum weight (connected) dominating sets in unit disk graphs. In: APPROX-RANDOM, pp. 3\u201314 (2006)","key":"935_CR1","DOI":"10.1007\/11830924_3"},{"doi-asserted-by":"crossref","unstructured":"Belgi, A., Nutov, Z.: An $$\\tilde{O} (\\log ^2 n)$$-approximation algorithm for 2-edge-connected dominating set. Inf. Process. Lett. (2021) (to appear)","key":"935_CR2","DOI":"10.1016\/j.ipl.2021.106175"},{"issue":"4","key":"935_CR3","doi-asserted-by":"publisher","first-page":"202","DOI":"10.1002\/net.10097","volume":"42","author":"X Cheng","year":"2003","unstructured":"Cheng, X., Huang, X., Li, D., Weili, W., Du, D.Z.: A polynomial-time approximation scheme for the minimum-connected dominating set in ad hoc wireless networks. Networks 42(4), 202\u2013208 (2003)","journal-title":"Networks"},{"issue":"1\u20133","key":"935_CR4","doi-asserted-by":"publisher","first-page":"165","DOI":"10.1016\/0012-365X(90)90358-O","volume":"86","author":"BN Clark","year":"1990","unstructured":"Clark, B.N., Colbourn, C.J., Johnson, D.S.: Unit disk graphs. Discrete Math. 86(1\u20133), 165\u2013177 (1990)","journal-title":"Discrete Math."},{"doi-asserted-by":"crossref","unstructured":"Das, B., Bharghavan, V.: Routing in ad-hoc networks using minimum connected dominating sets. In: IEEE International Conference on Communications, pp. 376-380 (1997)","key":"935_CR5","DOI":"10.1109\/ICC.1997.605303"},{"issue":"1","key":"935_CR6","doi-asserted-by":"publisher","first-page":"56","DOI":"10.1109\/PROC.1987.13705","volume":"75","author":"A Ephremides","year":"1987","unstructured":"Ephremides, A., Wieselthier, J.E., Baker, D.J.: A design concept for reliable mobile radio networks with frequency hopping signaling. Proc. IEEE 75(1), 56\u201373 (1987)","journal-title":"Proc. IEEE"},{"doi-asserted-by":"crossref","unstructured":"F\u00f6rster, K.T.: Approximating fault-tolerant domination in general graphs. In: ANALCO, pp. 25\u201332 (2013)","key":"935_CR7","DOI":"10.1137\/1.9781611973037.4"},{"issue":"11","key":"935_CR8","doi-asserted-by":"publisher","first-page":"3270","DOI":"10.1007\/s00453-017-0385-2","volume":"80","author":"T Fukunaga","year":"2018","unstructured":"Fukunaga, T.: Approximation algorithms for highly connected multi-dominating sets in unit disk graphs. Algorithmica 80(11), 3270\u20133292 (2018)","journal-title":"Algorithmica"},{"issue":"4","key":"935_CR9","doi-asserted-by":"publisher","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(4), 374\u2013387 (1998)","journal-title":"Algorithmica"},{"key":"935_CR10","doi-asserted-by":"publisher","first-page":"8","DOI":"10.1006\/jctb.1995.1002","volume":"63","author":"T Jord\u00e1n","year":"1995","unstructured":"Jord\u00e1n, T.: On the optimal vertex-connectivity augmentation. J. Combin. Theory Ser. B 63, 8\u201320 (1995)","journal-title":"J. Combin. Theory Ser. B"},{"issue":"1","key":"935_CR11","doi-asserted-by":"publisher","first-page":"104","DOI":"10.1006\/jagm.1995.1029","volume":"19","author":"P Klein","year":"1995","unstructured":"Klein, P., Ravi, R.: A nearly best-possible approximation algorithm for node-weighted Steiner trees. J. Algorithms 19(1), 104\u2013115 (1995)","journal-title":"J. Algorithms"},{"issue":"1","key":"935_CR12","doi-asserted-by":"publisher","first-page":"247","DOI":"10.1137\/S0097539703435753","volume":"35","author":"G Kortsarz","year":"2005","unstructured":"Kortsarz, G., Nutov, Z.: Approximating k-node connected subgraphs via critical graphs. SIAM J. Comput. 35(1), 247\u2013257 (2005)","journal-title":"SIAM J. Comput."},{"key":"935_CR13","doi-asserted-by":"publisher","first-page":"32","DOI":"10.1016\/j.tcs.2017.02.008","volume":"674","author":"G Kortsarz","year":"2017","unstructured":"Kortsarz, G., Nutov, Z.: Approximating source location and star survivable network problems. Theor. Comput. Sci. 674, 32\u201342 (2017)","journal-title":"Theor. Comput. Sci."},{"key":"935_CR14","doi-asserted-by":"publisher","first-page":"219","DOI":"10.1007\/BF01304873","volume":"23","author":"W Mader","year":"1972","unstructured":"Mader, W.: Ecken vom grad $$n$$ in minimalen $$n$$-fach zusammenh\u00e4ngenden graphen. Arch. Math. 23, 219\u2013224 (1972)","journal-title":"Arch. Math."},{"issue":"1","key":"935_CR15","doi-asserted-by":"publisher","first-page":"1:1","DOI":"10.1145\/2390176.2390177","volume":"9","author":"Z Nutov","year":"2012","unstructured":"Nutov, Z.: Approximating minimum cost connectivity problems via uncrossable bifamilies. ACM Trans. Algorithms 9(1), 1:1-1:16 (2012)","journal-title":"ACM Trans. Algorithms"},{"key":"935_CR16","doi-asserted-by":"publisher","first-page":"51","DOI":"10.1016\/j.jda.2012.08.001","volume":"17","author":"Z Nutov","year":"2012","unstructured":"Nutov, Z.: Approximating subset $$k$$-connectivity problems. J. Discrete Algorithms 17, 51\u201359 (2012)","journal-title":"J. Discrete Algorithms"},{"key":"935_CR17","doi-asserted-by":"publisher","first-page":"30","DOI":"10.1016\/j.ipl.2018.08.003","volume":"140","author":"Z Nutov","year":"2018","unstructured":"Nutov, Z.: Improved approximation algorithms for $$k$$-connected $$m$$-dominating set problems. Inf. Process. Lett. 140, 30\u201333 (2018)","journal-title":"Inf. Process. Lett."},{"key":"935_CR18","volume-title":"Handbook on Approximation Algorithms and Metaheuristics","author":"Z Nutov","year":"2018","unstructured":"Nutov, Z.: Chapter\u00a013: Node-connectivity survivable network problems. In: Gonzalez, T.F. (ed.) Handbook on Approximation Algorithms and Metaheuristics, vol. 2, 2nd edn. Chapman & Hall\/CRC, New York (2018)","edition":"2"},{"doi-asserted-by":"crossref","unstructured":"Nutov, Z.: 2-Node-connectivity network design. In: WAOA, pp. 220\u2013235 (2020)","key":"935_CR19","DOI":"10.1007\/978-3-030-80879-2_15"},{"issue":"2","key":"935_CR20","doi-asserted-by":"publisher","first-page":"925","DOI":"10.1109\/TNET.2016.2607723","volume":"25","author":"Y Shi","year":"2017","unstructured":"Shi, Y., Zhang, Z., Mo, Y., Du, D.Z.: Approximation algorithm for minimum weight fault-tolerant virtual backbone in unit disk graphs. IEEE\/ACM Trans. Netw. 25(2), 925\u2013933 (2017)","journal-title":"IEEE\/ACM Trans. Netw."},{"key":"935_CR21","doi-asserted-by":"publisher","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.: On approximation algorithms of $$k$$-connected $$m$$-dominating sets in disk graphs. Theor. Comput. Sci. 385, 49\u201359 (2007)","journal-title":"Theor. Comput. Sci."},{"doi-asserted-by":"crossref","unstructured":"Willson, J., Zhang, Z., Wu, W., Du, D.Z.: Fault-tolerant coverage with maximum lifetime in wireless sensor networks. In: INFOCOM, pp. 1364\u20131372 (2015)","key":"935_CR22","DOI":"10.1109\/INFOCOM.2015.7218513"},{"issue":"2","key":"935_CR23","doi-asserted-by":"publisher","first-page":"217","DOI":"10.1287\/ijoc.2017.0776","volume":"30","author":"Z Zhang","year":"2018","unstructured":"Zhang, Z., Zhou, J., Tang, S., Huang, X., Du, D.Z.: Computing minimum k-connected m-fold dominating set in general graphs. INFORMS J. Comput. 30(2), 217\u2013224 (2018)","journal-title":"INFORMS J. Comput."},{"issue":"4","key":"935_CR24","doi-asserted-by":"publisher","first-page":"342","DOI":"10.1007\/s10878-009-9229-6","volume":"18","author":"F Zou","year":"2009","unstructured":"Zou, F., Li, X., Gao, S., Weili, W.: Node-weighted Steiner tree approximation in unit disk graphs. J. Comb. Optim. 18(4), 342\u2013349 (2009)","journal-title":"J. Comb. Optim."},{"issue":"3","key":"935_CR25","doi-asserted-by":"publisher","first-page":"198","DOI":"10.1016\/j.tcs.2009.06.022","volume":"412","author":"F Zou","year":"2011","unstructured":"Zou, F., Wang, Y., XiaoHua, X., Li, X., Hongwei, D., Wan, P.J., Weili, W.: New approximations for minimum-weighted dominating sets and minimum-weighted connected dominating sets on unit disk graphs. Theor. Comput. Sci. 412(3), 198\u2013208 (2011)","journal-title":"Theor. Comput. Sci."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-022-00935-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-022-00935-x\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-022-00935-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,9,18]],"date-time":"2024-09-18T17:57:05Z","timestamp":1726682225000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-022-00935-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,2,16]]},"references-count":25,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2022,6]]}},"alternative-id":["935"],"URL":"https:\/\/doi.org\/10.1007\/s00453-022-00935-x","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2022,2,16]]},"assertion":[{"value":"19 November 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"11 January 2022","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"16 February 2022","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}