{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,9]],"date-time":"2026-04-09T18:22:25Z","timestamp":1775758945788,"version":"3.50.1"},"reference-count":19,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2014,1,30]],"date-time":"2014-01-30T00:00:00Z","timestamp":1391040000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Combinatorica"],"published-print":{"date-parts":[[2014,2]]},"DOI":"10.1007\/s00493-014-2773-4","type":"journal-article","created":{"date-parts":[[2014,1,30]],"date-time":"2014-01-30T07:53:16Z","timestamp":1391068396000},"page":"95-114","source":"Crossref","is-referenced-by-count":11,"title":["Approximating minimum-cost edge-covers of crossing biset-families"],"prefix":"10.1007","volume":"34","author":[{"given":"Zeev","family":"Nutov","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2014,1,30]]},"reference":[{"key":"2773_CR1","doi-asserted-by":"crossref","first-page":"25","DOI":"10.1016\/j.disopt.2012.10.002","volume":"10","author":"A Aazami","year":"2013","unstructured":"A. Aazami, J. Cheriyan and B. Laekhanukit: A bad example for the iterative rounding method for mincost k-connected spanning subgraphs, Discrete Optimization 10 (2013) 25\u201341.","journal-title":"Discrete Optimization"},{"key":"2773_CR2","volume-title":"Approximation algorithms for minimum-cost k-(S,T) connected digraphs","author":"J Cheriyan","year":"2010","unstructured":"J. Cheriyan and B. Laekhanukit: Approximation algorithms for minimum-cost k-(S,T) connected digraphs, manuscript, 2010."},{"key":"2773_CR3","volume-title":"Approximating minimum-cost k-node connected sub-graphs via independence-free graphs","author":"J Cheriyan","year":"2013","unstructured":"J. Cheriyan and L. V\u00e9gh: Approximating minimum-cost k-node connected sub-graphs via independence-free graphs, manuscript, 2013."},{"key":"2773_CR4","doi-asserted-by":"crossref","first-page":"1050","DOI":"10.1137\/S0097539701392287","volume":"4","author":"J Cheriyan","year":"2003","unstructured":"J. Cheriyan, S. Vempala and A. Vetta: An approximation algorithm for the minimum-cost k-vertex connected subgraph, SIAM J. Computing 4 (2003) 1050\u20131055.","journal-title":"SIAM J. Computing"},{"key":"2773_CR5","first-page":"153","volume-title":"STOC","author":"J Fackharoenphol","year":"2008","unstructured":"J. Fackharoenphol and B. Laekhanukit: An O(log2 k)-approximation algorithm for the k-vertex connected subgraph problem, in: STOC, 153\u2013158, 2008."},{"key":"2773_CR6","doi-asserted-by":"crossref","first-page":"1242","DOI":"10.1016\/j.dam.2008.03.040","volume":"157","author":"A Frank","year":"2009","unstructured":"A. Frank: Rooted k-connections in digraphs, Discrete Applied Math. 157 (2009) 1242\u20131254.","journal-title":"Discrete Applied Math."},{"key":"2773_CR7","doi-asserted-by":"crossref","first-page":"73","DOI":"10.1006\/jctb.1995.1044","volume":"65","author":"A Frank","year":"1995","unstructured":"A. Frank and T. Jord\u00e1n: Minimal edge-coverings of pairs of sets, J. of Comb. Theory B 65 (1995) 73\u2013110","journal-title":"J. of Comb. Theory B"},{"key":"2773_CR8","volume-title":"Iterative rounding approximation algorithms for degree bounded node-connectivity problems","author":"T Fukunaga","year":"2013","unstructured":"T. Fukunaga, Z. Nutov and R. Ravi: Iterative rounding approximation algorithms for degree bounded node-connectivity problems, manuscript, 2013."},{"key":"2773_CR9","doi-asserted-by":"crossref","first-page":"8","DOI":"10.1006\/jctb.1995.1002","volume":"63","author":"T Jord\u00e1n","year":"1995","unstructured":"T. Jord\u00e1n: On the optimal vertex-connectivity augmentation, J. on Comb. Theory B 63 (1995) 8\u201320.","journal-title":"J. on Comb. Theory B"},{"key":"2773_CR10","doi-asserted-by":"crossref","first-page":"704","DOI":"10.1137\/S0097539702416736","volume":"33","author":"G Kortsarz","year":"2004","unstructured":"G. Kortsarz, R. Krauthgamer and J. R. Lee: Hardness of approximation for vertex-connectivity network design problems, SIAM Journal on Computing 33 (2004) 704\u2013720.","journal-title":"SIAM Journal on Computing"},{"key":"2773_CR11","doi-asserted-by":"crossref","first-page":"247","DOI":"10.1137\/S0097539703435753","volume":"35","author":"G Kortsarz","year":"2005","unstructured":"G. Kortsarz and Z. Nutov: Approximating k-node connected subgraphs via critical graphs, SIAM Journal on Computing 35 (2005) 247\u2013257.","journal-title":"SIAM Journal on Computing"},{"key":"2773_CR12","volume-title":"Chapter 58 in Approximation Algorithms and Metaheuristics","author":"G Kortsarz","year":"2007","unstructured":"G. Kortsarz and Z. Nutov: Approximating minimum-cost connectivity problems, in: T. F. Gonzalez, editor, Chapter 58 in Approximation Algorithms and Metaheuristics. Chapman & Hall\/CRC, 2007."},{"key":"2773_CR13","first-page":"13","volume-title":"ICALP","author":"B Laekhanukit","year":"2011","unstructured":"B. Laekhanukit: An improved approximation algorithm for minimum-cost subset k-connectivity, in: ICALP, 13\u201324, 2011."},{"key":"2773_CR14","doi-asserted-by":"crossref","first-page":"2122","DOI":"10.1016\/j.tcs.2009.01.036","volume":"410","author":"Y Lando","year":"2009","unstructured":"Y. Lando and Z. Nutov: Inapproximability of survivable networks, Theortical Computer Science 410 (2009) 2122\u20132125.","journal-title":"Theortical Computer Science"},{"key":"2773_CR15","volume-title":"Approximating minimum cost connectivity problems via uncrossable bifamilies","author":"Z Nutov","year":"2010","unstructured":"Z. Nutov: Approximating minimum cost connectivity problems via uncrossable bifamilies, manuscript 2010. Preliminary version in FOCS 2009, 17-426."},{"key":"2773_CR16","first-page":"922","volume-title":"SODA","author":"Z Nutov","year":"2009","unstructured":"Z. Nutov: An almost O(logk)-approximation for k-connected subgraphs, in: SODA, 922\u2013931, 2009."},{"key":"2773_CR17","first-page":"9","volume-title":"WAOA","author":"Z Nutov","year":"2011","unstructured":"Z. Nutov: Approximating subset k-connectivity problems, in: WAOA, 9\u201320, 2011."},{"key":"2773_CR18","doi-asserted-by":"crossref","first-page":"21","DOI":"10.1007\/BF02523686","volume":"18","author":"R Ravi","year":"1997","unstructured":"R. Ravi and D. P. Williamson: An approximation algorithm for minimum-cost vertex-connectivity problems, Algorithmica 18 (1997) 21\u201343.","journal-title":"Algorithmica"},{"key":"2773_CR19","doi-asserted-by":"crossref","first-page":"98","DOI":"10.1007\/s00453-002-0970-9","volume":"34","author":"R Ravi","year":"2002","unstructured":"R. Ravi and D. P. Williamson: Erratum: an approximation algorithm for minimum-cost vertex-connectivity problems, Algorithmica 34 (2002) 98\u2013107.","journal-title":"Algorithmica"}],"container-title":["Combinatorica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00493-014-2773-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00493-014-2773-4\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00493-014-2773-4","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,29]],"date-time":"2019-05-29T01:32:49Z","timestamp":1559093569000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00493-014-2773-4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,1,30]]},"references-count":19,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2014,2]]}},"alternative-id":["2773"],"URL":"https:\/\/doi.org\/10.1007\/s00493-014-2773-4","relation":{},"ISSN":["0209-9683","1439-6912"],"issn-type":[{"value":"0209-9683","type":"print"},{"value":"1439-6912","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014,1,30]]}}}