{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,9]],"date-time":"2024-09-09T06:17:08Z","timestamp":1725862628088},"publisher-location":"Berlin, Heidelberg","reference-count":24,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783662531730"},{"type":"electronic","value":"9783662531747"}],"license":[{"start":{"date-parts":[[2016,1,1]],"date-time":"2016-01-01T00:00:00Z","timestamp":1451606400000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2016]]},"DOI":"10.1007\/978-3-662-53174-7_15","type":"book-chapter","created":{"date-parts":[[2016,8,4]],"date-time":"2016-08-04T10:50:06Z","timestamp":1470307806000},"page":"203-218","source":"Crossref","is-referenced-by-count":2,"title":["Approximating Source Location and Star Survivable Network Problems"],"prefix":"10.1007","author":[{"given":"Guy","family":"Kortsarz","sequence":"first","affiliation":[]},{"given":"Zeev","family":"Nutov","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2016,8,5]]},"reference":[{"key":"15_CR1","doi-asserted-by":"crossref","first-page":"54","DOI":"10.1006\/jagm.2001.1203","volume":"42","author":"K Arata","year":"2002","unstructured":"Arata, K., Iwata, S., Makino, K., Fujishige, S.: Locating sources to meet flow demands in undirected networks. J. Algorithms 42, 54\u201368 (2002)","journal-title":"J. Algorithms"},{"issue":"1\u20132","key":"15_CR2","doi-asserted-by":"crossref","first-page":"179","DOI":"10.1016\/S0304-3975(99)00130-9","volume":"250","author":"J Bar-Ilan","year":"2001","unstructured":"Bar-Ilan, J., Kortsarz, G., Peleg, D.: Generalized submodular cover problems and applications. Theor. Comput. Sci. 250(1\u20132), 179\u2013200 (2001)","journal-title":"Theor. Comput. Sci."},{"key":"15_CR3","doi-asserted-by":"crossref","unstructured":"Chuzhoy, J., Khanna, S.: An $${O}(k^3 \\log n)$$ -approximation algorithms for vertex-connectivity survivable network design. In: FOCS, pp. 437\u2013441 (2009)","DOI":"10.1109\/FOCS.2009.38"},{"issue":"1","key":"15_CR4","doi-asserted-by":"crossref","first-page":"25","DOI":"10.1137\/0405003","volume":"5","author":"A Frank","year":"1992","unstructured":"Frank, A.: Augmenting graphs to meet edge-connectivity requirements. SIAM J. Discrete Math. 5(1), 25\u201353 (1992)","journal-title":"SIAM J. Discrete Math."},{"issue":"3","key":"15_CR5","doi-asserted-by":"crossref","first-page":"275","DOI":"10.1002\/jgt.3190170302","volume":"17","author":"A Frank","year":"1993","unstructured":"Frank, A., Ibaraki, T., Nagamochi, H.: On sparse subgraphs preserving connectivity properties. J. Graph Theor. 17(3), 275\u2013281 (1993)","journal-title":"J. Graph Theor."},{"issue":"115","key":"15_CR6","doi-asserted-by":"crossref","first-page":"329","DOI":"10.1016\/0024-3795(89)90469-2","volume":"114","author":"A Frank","year":"1989","unstructured":"Frank, A., Tardos, E.: An application of submodular flows. Linear Algebra Appl. 114(115), 329\u2013348 (1989)","journal-title":"Linear Algebra Appl."},{"key":"15_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"428","DOI":"10.1007\/978-3-642-20877-5_42","volume-title":"Theory and Applications of Models of Computation","author":"T Fukunaga","year":"2011","unstructured":"Fukunaga, T.: Approximating minimum cost source location problems with local vertex-connectivity demands. In: Ogihara, M., Tarui, J. (eds.) TAMC 2011. LNCS, vol. 6648, pp. 428\u2013439. Springer, Heidelberg (2011)"},{"key":"15_CR8","unstructured":"Goemans, M., Goldberg, A., Plotkin, S., Shmoys, D., Tardos, E., Williamson, D.: Improved approximation algorithms for network design problems. In: SODA, pp. 223\u2013232 (1994)"},{"key":"15_CR9","doi-asserted-by":"crossref","first-page":"570","DOI":"10.1016\/j.jda.2009.06.003","volume":"7","author":"T Ishii","year":"2009","unstructured":"Ishii, T.: Greedy approximation for source location problem with vertex-connectivity requirements in undirected graphs. J. Discrete Algorithms 7, 570\u2013578 (2009)","journal-title":"J. Discrete Algorithms"},{"issue":"4","key":"15_CR10","doi-asserted-by":"crossref","first-page":"427","DOI":"10.1080\/1055-6780309510593","volume":"18","author":"H Ito","year":"2003","unstructured":"Ito, H., Makino, K., Arata, K., Honami, S., Itatsu, Y., Fujishige, S.: Source location problem with flow requirements in directed networks. Optim. Methods Softw. 18(4), 427\u2013435 (2003)","journal-title":"Optim. Methods Softw."},{"issue":"1","key":"15_CR11","doi-asserted-by":"crossref","first-page":"39","DOI":"10.1007\/s004930170004","volume":"21","author":"K Jain","year":"2001","unstructured":"Jain, K.: A factor 2 approximation algorithm for the generalized steiner network problem. Combinatorica 21(1), 39\u201360 (2001)","journal-title":"Combinatorica"},{"key":"15_CR12","doi-asserted-by":"crossref","unstructured":"Kortsarz, G., Nutov, Z.: Approximating minimum cost connectivity problems. In: Gonzales, T.F. (ed.) Approximation Algorithms and Metaheuristics, Ch. 58 (2007)","DOI":"10.1201\/9781420010749.ch58"},{"issue":"5","key":"15_CR13","doi-asserted-by":"crossref","first-page":"662","DOI":"10.1016\/j.jcss.2007.05.002","volume":"74","author":"G Kortsarz","year":"2008","unstructured":"Kortsarz, G., Nutov, Z.: Tight approximation algorithm for connectivity augmentation problems. J. Comput. Syst. Sci. 74(5), 662\u2013670 (2008)","journal-title":"J. Comput. Syst. Sci."},{"key":"15_CR14","doi-asserted-by":"crossref","unstructured":"Laekhanukit, B.: Parameters of two-prover-one-round game and the hardness of connectivity problems. In: SODA, pp. 1626\u20131643 (2014)","DOI":"10.1137\/1.9781611973402.118"},{"key":"15_CR15","doi-asserted-by":"crossref","first-page":"383","DOI":"10.1016\/0012-365X(75)90058-8","volume":"13","author":"L Lov\u00e1sz","year":"1975","unstructured":"Lov\u00e1sz, L.: On the ratio of optimal integral and fractional covers. Discrete Math. 13, 383\u2013390 (1975)","journal-title":"Discrete Math."},{"key":"15_CR16","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511721649","volume-title":"Algorithmic Aspects of Graph Connectivity, Ch. 9","author":"H Nagamochi","year":"2008","unstructured":"Nagamochi, H., Ibaraki, T.: Algorithmic Aspects of Graph Connectivity, Ch. 9. Cambridge University Press, Cambridge (2008)"},{"key":"15_CR17","doi-asserted-by":"crossref","first-page":"287","DOI":"10.1016\/S0020-0190(01)00183-1","volume":"80","author":"H Nagamochi","year":"2001","unstructured":"Nagamochi, H., Ishii, T., Ito, H.: Minimum cost source location problem with vertex-connectivity requirements in digraphs. IPL 80, 287\u2013294 (2001)","journal-title":"IPL"},{"issue":"1","key":"15_CR18","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/2390176.2390177","volume":"9","author":"Z Nutov","year":"2012","unstructured":"Nutov, Z.: Approximating minimum cost connectivity problems via uncrossable bifamilies. Trans. Algorithms 9(1), 1 (2012)","journal-title":"Trans. Algorithms"},{"issue":"1\u20132","key":"15_CR19","doi-asserted-by":"crossref","first-page":"398","DOI":"10.1007\/s00453-011-9538-x","volume":"63","author":"Z Nutov","year":"2012","unstructured":"Nutov, Z.: Approximating node-connectivity augmentation problems. Algorithmica 63(1\u20132), 398\u2013410 (2012)","journal-title":"Algorithmica"},{"key":"15_CR20","doi-asserted-by":"crossref","first-page":"555","DOI":"10.1007\/s00453-007-9012-y","volume":"50","author":"M Sakashita","year":"2008","unstructured":"Sakashita, M., Makino, K., Fujishige, S.: Minimum cost source location problems with flow requirements. Algorithmica 50, 555\u2013583 (2008)","journal-title":"Algorithmica"},{"key":"15_CR21","volume-title":"Combinatorial Optimization Polyhedra and Efficiency","author":"A Schrijver","year":"2004","unstructured":"Schrijver, A.: Combinatorial Optimization Polyhedra and Efficiency. Springer, Heidelberg (2004)"},{"key":"15_CR22","first-page":"1989","volume":"E73","author":"H Tamura","year":"1990","unstructured":"Tamura, H., Sengoku, M., Shinoda, S., Abe, T.: Location problems on undirected flow networks. IEICE Trans. E73, 1989\u20131993 (1990)","journal-title":"IEICE Trans."},{"key":"15_CR23","unstructured":"Vakilian, A.: Node-weighted prize-collecting network design problems. M.Sc. thesis (2013)"},{"key":"15_CR24","doi-asserted-by":"crossref","first-page":"385","DOI":"10.1007\/BF02579435","volume":"2","author":"LA Wolsey","year":"1982","unstructured":"Wolsey, L.A.: An analysis of the greedy algorithm for the submodular set covering problem. Combinatorica 2, 385\u2013393 (1982)","journal-title":"Combinatorica"}],"container-title":["Lecture Notes in Computer Science","Graph-Theoretic Concepts in Computer Science"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-662-53174-7_15","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2017,6,24]],"date-time":"2017-06-24T15:57:45Z","timestamp":1498319865000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-662-53174-7_15"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016]]},"ISBN":["9783662531730","9783662531747"],"references-count":24,"URL":"https:\/\/doi.org\/10.1007\/978-3-662-53174-7_15","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2016]]}}}