{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,3,30]],"date-time":"2022-03-30T03:23:30Z","timestamp":1648610610456},"reference-count":29,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2014,12,25]],"date-time":"2014-12-25T00:00:00Z","timestamp":1419465600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Comb Optim"],"published-print":{"date-parts":[[2016,4]]},"DOI":"10.1007\/s10878-014-9823-0","type":"journal-article","created":{"date-parts":[[2014,12,24]],"date-time":"2014-12-24T03:49:25Z","timestamp":1419392965000},"page":"1280-1297","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Improved approximation algorithms for single-tiered relay placement"],"prefix":"10.1007","volume":"31","author":[{"given":"Gruia","family":"Calinescu","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Benjamin","family":"Grimmer","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Satyajayant","family":"Misra","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sutep","family":"Tongngam","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Guoliang","family":"Xue","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Weiyi","family":"Zhang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2014,12,25]]},"reference":[{"issue":"5","key":"9823_CR1","doi-asserted-by":"crossref","first-page":"753","DOI":"10.1145\/290179.290180","volume":"45","author":"S Arora","year":"1998","unstructured":"Arora S (1998) Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems. JACM 45(5):753\u2013782","journal-title":"JACM"},{"key":"9823_CR2","doi-asserted-by":"crossref","first-page":"21","DOI":"10.1006\/jagm.1999.1006","volume":"32","author":"V Auletta","year":"1999","unstructured":"Auletta V, Dinitz Y, Nutov Z, Parente D (1999) A 2-approximation algorithm for finding an optimum 3-vertex-connected spanning subgraph. J Algorithms 32:21\u201330","journal-title":"J Algorithms"},{"issue":"3","key":"9823_CR3","doi-asserted-by":"crossref","first-page":"857","DOI":"10.1137\/S0097539795281086","volume":"26","author":"A Borchers","year":"1997","unstructured":"Borchers A, Du D-Z (1997) The k-Steiner ratio in graphs. SIAM J Comput 26(3):857\u2013869","journal-title":"SIAM J Comput"},{"key":"9823_CR4","doi-asserted-by":"crossref","DOI":"10.1017\/9781139171854","volume-title":"Metric spaces: iteration and application","author":"V Bryant","year":"1985","unstructured":"Bryant V (1985) Metric spaces: iteration and application. Cambridge University Press, Cambridge"},{"key":"9823_CR5","first-page":"366","volume-title":"Networking (2) lecture notes in computer science","author":"G Calinescu","year":"2012","unstructured":"Calinescu G (2012) Relay placement for two-connectivity. In: Bestak R, Kencl L, Li LE, Widmer J, Yin H (eds) Networking (2) lecture notes in computer science, vol 7290. Springer, Berlin, pp 366\u2013377"},{"key":"9823_CR6","doi-asserted-by":"crossref","first-page":"286","DOI":"10.1007\/978-3-540-88582-5_28","volume-title":"Wireless algorithms, systems, and applications, of lecture notes in computer science","author":"G Calinescu","year":"2008","unstructured":"Calinescu G, Tongngam S (2008) Relay nodes in wireless sensor networks. In: Li Y, Huynh DT, Das S, Du D-Z (eds) Wireless algorithms, systems, and applications, of lecture notes in computer science, vol 5258. Springer, Berlin, pp 286\u2013297"},{"issue":"12","key":"9823_CR7","doi-asserted-by":"crossref","first-page":"83","DOI":"10.1016\/S0304-3975(00)00182-1","volume":"262","author":"D Chen","year":"2001","unstructured":"Chen D, Du D-Z, Hu X-D, Lin G-H, Wang L, Xue G (2001) Approximations for Steiner trees with minimum number of Steiner points. Theor Comput Sci 262(12):83\u201399","journal-title":"Theor Comput Sci"},{"issue":"3","key":"9823_CR8","doi-asserted-by":"crossref","first-page":"347","DOI":"10.1007\/s11276-006-0724-8","volume":"14","author":"X Cheng","year":"2008","unstructured":"Cheng X, Du D-Z, Wang L, Xu B (2008) Relay sensor placement in wireless sensor networks. Wirel. Netw. 14(3):347\u2013355","journal-title":"Wirel. Netw."},{"key":"9823_CR9","unstructured":"Cohen N, Nutov Z (2013) Approximating 0,1,2-survivable networks with minimum number of Steiner points. CoRR, arXiv:1304.7571"},{"key":"9823_CR10","doi-asserted-by":"crossref","first-page":"356","DOI":"10.1007\/978-3-540-87744-8_30","volume-title":"Algorithms - ESA 2008, lecture notes in computer science","author":"A Efrat","year":"2008","unstructured":"Efrat A, Fekete SP, Gaddehosur PR, Mitchell JS, Polishchuk V, Suomela J (2008) Improved approximation algorithms for relay placement. In: Halperin D, Mehlhorn K (eds) Algorithms - ESA 2008, lecture notes in computer science, vol 5193. Springer, Berlin \/ Heidelberg, pp 356\u2013367"},{"key":"9823_CR11","unstructured":"Efrat A, Fekete S.P, Gaddehosur P.R, Mitchell J.S, Polishchuk V, Suomela J Improved approximation algorithms for relay placement. from http:\/\/webstaff.itn.liu.se\/valpo40\/pages\/papers.html"},{"key":"9823_CR12","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":"9823_CR13","volume-title":"Connections in combinatorial optimization","author":"A Frank","year":"2011","unstructured":"Frank A (2011) Connections in combinatorial optimization. Oxford University Press, Oxford"},{"issue":"115","key":"9823_CR14","first-page":"320","volume":"114","author":"A Frank","year":"1989","unstructured":"Frank A, Tardos E (1989) An application of submodular flows. Linear Algebr Appl 114(115):320\u2013348","journal-title":"Linear Algebr Appl"},{"key":"9823_CR15","unstructured":"Gabow HN (1993) A representation for crossing set families with applications to submodular flow problems. In: Proceedings of the fourth annual ACM-SIAM Symposium on Discrete algorithms, SODA \u201993, pages 202\u2013211, Philadelphia, PA, USA. Society for Industrial and Applied Mathematics"},{"key":"9823_CR16","doi-asserted-by":"crossref","first-page":"235","DOI":"10.1007\/978-1-4613-0255-1_7","volume-title":"Steiner trees in industries","author":"C Gr\u00f6pl","year":"2001","unstructured":"Gr\u00f6pl C, Hougardy S, Nierhoff T, Pr\u00f6mel HJ (2001) Approximation algorithms for the Steiner tree problem in graphs. In: Du D-Z, Cheng X (eds) Steiner trees in industries. Kluwer Academic Publishers, Dordrecht, pp 235\u2013279"},{"key":"9823_CR17","doi-asserted-by":"crossref","unstructured":"Kashyap A, Khuller S, Shayman M (2006) Relay placement for higher order connectivity in wireless sensor networks. INFOCOM 2006. 25th IEEE International Conference on Computer Communications. Proceedings, pp 1\u201312","DOI":"10.1109\/INFOCOM.2006.273"},{"issue":"4","key":"9823_CR18","doi-asserted-by":"crossref","first-page":"206","DOI":"10.1016\/j.comgeo.2010.11.002","volume":"44","author":"A Kashyap","year":"2011","unstructured":"Kashyap A, Khuller S, Shayman MA (2011) Relay placement for fault tolerance in wireless networks in higher dimensions. Comput Geom 44(4):206\u2013215","journal-title":"Comput Geom"},{"key":"9823_CR19","doi-asserted-by":"crossref","first-page":"433","DOI":"10.1006\/jagm.1996.0052","volume":"21","author":"S Khuller","year":"1996","unstructured":"Khuller S, Raghavachari B (1996) Improved approximation algorithms for uniform connectivity problems. J Algorithms 21:433\u2013450","journal-title":"J Algorithms"},{"issue":"2","key":"9823_CR20","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 (1999) Steiner tree problem with minimum number of Steiner points and bounded edge-length. Inf Process Lett 69(2):53\u201357","journal-title":"Inf Process Lett"},{"issue":"1","key":"9823_CR21","doi-asserted-by":"crossref","first-page":"134","DOI":"10.1109\/TC.2007.250629","volume":"56","author":"EL Lloyd","year":"2007","unstructured":"Lloyd EL, Xue G (2007) Relay node placement in wireless sensor networks. IEEE Trans Comput 56(1):134\u2013138","journal-title":"IEEE Trans Comput"},{"issue":"4","key":"9823_CR22","doi-asserted-by":"crossref","first-page":"165","DOI":"10.1016\/S0020-0190(00)00095-8","volume":"75","author":"II Mandoiu","year":"2000","unstructured":"Mandoiu II, Zelikovsky AZ (2000) A note on the MST heuristic for bounded edge-length Steiner trees with minimum number of Steiner points. Inf Process Lett 75(4):165\u2013167","journal-title":"Inf Process Lett"},{"issue":"2","key":"9823_CR23","doi-asserted-by":"crossref","first-page":"122","DOI":"10.1016\/j.aml.2005.03.011","volume":"19","author":"H Martini","year":"2006","unstructured":"Martini H, Swanepoel KJ (2006) Low-degree minimal spanning trees in normed spaces. Appl Math Lett 19(2):122\u2013125","journal-title":"Appl Math Lett"},{"issue":"19","key":"9823_CR24","doi-asserted-by":"crossref","first-page":"1136","DOI":"10.1016\/j.ipl.2009.07.013","volume":"109","author":"Z Nutov","year":"2009","unstructured":"Nutov Z, Yaroshevitch A (2009) Wireless network design via 3-decompositions. Inf Process Lett 109(19):1136\u20131140","journal-title":"Inf Process Lett"},{"issue":"2","key":"9823_CR25","doi-asserted-by":"crossref","first-page":"151","DOI":"10.1007\/BF02570700","volume":"14","author":"G Robins","year":"1995","unstructured":"Robins G, Salowe JS (1995) Low-degree minimum spanning trees. Discret Comput Geom 14(2):151\u2013165","journal-title":"Discret Comput Geom"},{"key":"9823_CR26","doi-asserted-by":"crossref","first-page":"490","DOI":"10.1016\/j.comcom.2004.12.032","volume":"29","author":"J Tang","year":"2006","unstructured":"Tang J, Hao B, Sen A (2006) Relay node placement in large scale wireless sensor networks. Comput Commun 29:490\u2013501","journal-title":"Comput Commun"},{"key":"9823_CR27","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 Virginia"},{"issue":"5","key":"9823_CR28","doi-asserted-by":"crossref","first-page":"463","DOI":"10.1007\/BF01187035","volume":"9","author":"AZ Zelikovsky","year":"1993","unstructured":"Zelikovsky AZ (1993) An 11\/6-approximation algorithm for the network Steiner problem. Algorithmica 9(5):463\u2013470","journal-title":"Algorithmica"},{"key":"9823_CR29","doi-asserted-by":"crossref","unstructured":"Zhang W, Xue G, Misra S (2007) Fault-tolerant relay node placement in wireless sensor networks: Problems and algorithms. INFOCOM 2007. Proceedings 26th IEEE International Conference on Computer Communications. pp 1649\u20131657","DOI":"10.1109\/INFCOM.2007.193"}],"container-title":["Journal of Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-014-9823-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10878-014-9823-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-014-9823-0","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,18]],"date-time":"2019-08-18T23:48:57Z","timestamp":1566172137000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10878-014-9823-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,12,25]]},"references-count":29,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2016,4]]}},"alternative-id":["9823"],"URL":"https:\/\/doi.org\/10.1007\/s10878-014-9823-0","relation":{},"ISSN":["1382-6905","1573-2886"],"issn-type":[{"value":"1382-6905","type":"print"},{"value":"1573-2886","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014,12,25]]}}}