{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,13]],"date-time":"2026-01-13T07:38:21Z","timestamp":1768289901046,"version":"3.49.0"},"reference-count":38,"publisher":"Springer Science and Business Media LLC","issue":"5","license":[{"start":{"date-parts":[[2024,10,1]],"date-time":"2024-10-01T00:00:00Z","timestamp":1727740800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2024,10,1]],"date-time":"2024-10-01T00:00:00Z","timestamp":1727740800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2024,10]]},"DOI":"10.1007\/s00224-024-10175-x","type":"journal-article","created":{"date-parts":[[2024,10,2]],"date-time":"2024-10-02T03:32:39Z","timestamp":1727839959000},"page":"1468-1485","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Approximation algorithms for node and element connectivity augmentation problems"],"prefix":"10.1007","volume":"68","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":[[2024,10,2]]},"reference":[{"key":"10175_CR1","doi-asserted-by":"crossref","unstructured":"Adjiashvili, D.: Beating approximation factor two for weighted tree augmentation with bounded costs. ACM Trans. Algorithms. 15(2), 19:1\u201319:26 (2019)","DOI":"10.1145\/3182395"},{"issue":"1","key":"10175_CR2","doi-asserted-by":"publisher","first-page":"995","DOI":"10.1007\/s10107-022-01854-z","volume":"199","author":"H Angelidakis","year":"2023","unstructured":"Angelidakis, H., Denesik, D.H., Sanit\u00e0, L.: Node connectivity augmentation via iterative randomized rounding. Math. Program. 199(1), 995\u20131031 (2023)","journal-title":"Math. Program."},{"key":"10175_CR3","doi-asserted-by":"publisher","first-page":"457","DOI":"10.1007\/s101070050033","volume":"84","author":"J Bang-Jensen","year":"1999","unstructured":"Bang-Jensen, J., Jackson, B.: Augmenting hypergraphs by edges of size two. Math. Programming. 84, 457\u2013481 (1999)","journal-title":"Math. Programming."},{"key":"10175_CR4","first-page":"800","volume":"I","author":"M Basavaraju","year":"2014","unstructured":"Basavaraju, M., Fomin, F.V., Golovach, P.A., Misra, P., Ramanujan, M.S., Saurabh, S.: Parameterized algorithms to preserve connectivity. In ICALP, Part I, 800\u2013811 (2014)","journal-title":"In ICALP, Part"},{"key":"10175_CR5","doi-asserted-by":"publisher","first-page":"483","DOI":"10.1007\/s101070050034","volume":"84","author":"A Bencz\u00far","year":"1999","unstructured":"Bencz\u00far, A., Frank, A.: Covering symmetric supermodular functions by graphs. Math. Programming. 84, 483\u2013503 (1999)","journal-title":"Math. Programming."},{"issue":"4","key":"10175_CR6","doi-asserted-by":"publisher","first-page":"373","DOI":"10.1007\/s00493-012-2548-8","volume":"32","author":"A Bern\u00e1th","year":"2012","unstructured":"Bern\u00e1th, A., Kir\u00e1ly, T.: A unifying approach to splitting-off. Combinatorica 32(4), 373\u2013401 (2012)","journal-title":"Combinatorica"},{"issue":"3","key":"10175_CR7","doi-asserted-by":"publisher","first-page":"718","DOI":"10.1137\/21M1421143","volume":"52","author":"J Byrka","year":"2023","unstructured":"Byrka, J., Grandoni, F., Ameli, A.J.: Breaching the 2-approximation barrier for connectivity augmentation: a reduction to steiner tree. SIAM J. Comput. 52(3), 718\u2013739 (2023)","journal-title":"SIAM J. Comput."},{"key":"10175_CR8","doi-asserted-by":"crossref","unstructured":"Byrka, J., Grandoni, F., Rothvo\u00df, T., Sanit\u00e1, L.: Steiner tree approximation via iterative randomized rounding. J. ACM. 60(1),6:1\u20136:33 (2013)","DOI":"10.1145\/2432622.2432628"},{"key":"10175_CR9","doi-asserted-by":"crossref","unstructured":"Cecchetto, F., Traub, V., Zenklusen, R.: Bridging the gap between tree and connectivity augmentation: Unified and stronger approaches. In STOC, page 370\u2013383 (2021)","DOI":"10.1145\/3406325.3451086"},{"key":"10175_CR10","doi-asserted-by":"crossref","unstructured":"Cecchetto, F., Traub, V., Zenklusen, R.: Better-than-4\/3-approximations for leaf-to-leaf tree and connectivity augmentation (2022). arXiv:2204.06944","DOI":"10.1007\/s10107-023-02018-3"},{"issue":"4","key":"10175_CR11","doi-asserted-by":"publisher","first-page":"399","DOI":"10.1016\/j.orl.2008.01.009","volume":"36","author":"J Cheriyan","year":"2008","unstructured":"Cheriyan, J., Karloff, H., Khandekar, R., Koenemann, J.: On the integrality ratio for tree augmentation. Operation Research Letters. 36(4), 399\u2013401 (2008)","journal-title":"Operation Research Letters."},{"key":"10175_CR12","doi-asserted-by":"publisher","first-page":"67","DOI":"10.1016\/j.tcs.2013.04.004","volume":"489\u2013490","author":"N Cohen","year":"2013","unstructured":"Cohen, N., Nutov, Z.: A $$(1+\\ln 2)$$-approximation algorithm for minimum-cost $$2$$-edge-connectivity augmentation of trees with constant radius. Theoret. Comput. Sci. 489\u2013490, 67\u201374 (2013)","journal-title":"Theoret. Comput. Sci."},{"key":"10175_CR13","unstructured":"Dinic, E.A., Karzanov, A.V., Lomonosov, M.V.: On the structure of a family of minimal weighted cuts in a graph. Studies in Discrete Optimization, page 290\u2013306 (1976)"},{"key":"10175_CR14","doi-asserted-by":"crossref","unstructured":"Dinitz, Y., Nutov, Z.: A 2-level cactus model for the system of minimum and minimum+1 edge-cuts in a graph and its incremental maintenance. In STOC, pages 509\u2013518 (1995)","DOI":"10.1145\/225058.225268"},{"key":"10175_CR15","doi-asserted-by":"crossref","unstructured":"Even, G., Feldman, J., Kortsarz, G., Nutov, Z.: A $$1.8$$-approximation algorithm for augmenting edge-connectivity of a graph from 1 to 2. ACM Transactions on Algorithms. 5(2) (2009)","DOI":"10.1145\/1497290.1497297"},{"key":"10175_CR16","doi-asserted-by":"crossref","unstructured":"Fiorini, S., Gro\u00df, M., K\u00f6nemann, J., Sanit\u00e1, L.: A $$\\frac{3}{2}$$-approximation algorithm for tree augmentation via chv\u00e1tal-gomory cuts. In SODA, pages 817\u2013831 (2018)","DOI":"10.1137\/1.9781611975031.53"},{"issue":"3","key":"10175_CR17","doi-asserted-by":"publisher","first-page":"505","DOI":"10.1007\/s101070050035","volume":"84","author":"T Fleiner","year":"1999","unstructured":"Fleiner, T., Jord\u00e1n, T.: Coverings and structure of crossing families. Math. Program. 84(3), 505\u2013518 (1999)","journal-title":"Math. Program."},{"issue":"5","key":"10175_CR18","doi-asserted-by":"publisher","first-page":"838","DOI":"10.1016\/j.jcss.2005.05.006","volume":"72","author":"L Fleischer","year":"2006","unstructured":"Fleischer, L., Jain, K., Williamson, D.P.: Iterative rounding 2-approximation algorithms for minimum-cost vertex connectivity problems. J. Comput. Syst. Sci. 72(5), 838\u2013867 (2006)","journal-title":"J. Comput. Syst. Sci."},{"key":"10175_CR19","unstructured":"Frank, A.: Connections in Combinatorial Optimization. Oxford University Press (2011)"},{"key":"10175_CR20","unstructured":"Frank, A., Jord\u00e1n, T.: Graph connectivity augmentation. In Thulasiraman, K., Arumugam, S., Brandstadt, A., Nishizeki, T., (editors), Handbook of Graph Theory, Combinatorial Optimization, and Algorithms, chapter\u00a014, pages 313\u2013346. CRC Press (2015)"},{"key":"10175_CR21","doi-asserted-by":"publisher","first-page":"270","DOI":"10.1137\/0210019","volume":"10","author":"G Frederickson","year":"1981","unstructured":"Frederickson, G., J\u00e1j\u00e1, J.: Approximation algorithms for several graph augmentation problems. SIAM J. Computing. 10, 270\u2013283 (1981)","journal-title":"SIAM J. Computing."},{"issue":"6","key":"10175_CR22","doi-asserted-by":"publisher","first-page":"985","DOI":"10.1007\/s00224-020-10025-6","volume":"65","author":"W G\u00e1lvez","year":"2021","unstructured":"G\u00e1lvez, W., Grandoni, F., Ameli, A.J., Sornat, K.: On the cycle augmentation problem: Hardness and approximation algorithms. Theory Comput. Syst. 65(6), 985\u20131008 (2021)","journal-title":"Theory Comput. Syst."},{"key":"10175_CR23","doi-asserted-by":"crossref","unstructured":"Grandoni, F., Kalaitzis, C., Zenklusen, R.: Improved approximation for tree augmentation: saving by rewiring. In STOC, pages 632\u2013645 (2018)","DOI":"10.1145\/3188745.3188898"},{"key":"10175_CR24","unstructured":"Khuller, S.: Approximation algorithms for finding highly connected subgraphs. In Hochbaum, D., editor, Approximation Algorithms for NP-hard problems, chapter\u00a06, pages 236\u2013265. PWS (1995)"},{"issue":"2","key":"10175_CR25","doi-asserted-by":"publisher","first-page":"214","DOI":"10.1006\/jagm.1993.1010","volume":"14","author":"S Khuller","year":"1993","unstructured":"Khuller, S., Thurimella, R.: Approximation algorithms for graph augmentation. J. Algorithms 14(2), 214\u2013225 (1993)","journal-title":"J. Algorithms"},{"issue":"6","key":"10175_CR26","doi-asserted-by":"publisher","first-page":"723","DOI":"10.1016\/j.dam.2009.12.011","volume":"158","author":"Z Kir\u00e1ly","year":"2010","unstructured":"Kir\u00e1ly, Z., Cosh, B., Jackson, B.: Local edge-connectivity augmentation in hypergraphs is NP-complete. Discret. Appl. Math. 158(6), 723\u2013727 (2010)","journal-title":"Discret. Appl. Math."},{"key":"10175_CR27","doi-asserted-by":"crossref","unstructured":"Kortsarz, G., Nutov, Z.: A simplified $$1.5$$-approximation algorithm for augmenting edge-connectivity of a graph from 1 to 2. ACM Transactions on Algorithms. 12(2), 23 (2016)","DOI":"10.1145\/2786981"},{"key":"10175_CR28","doi-asserted-by":"publisher","first-page":"218","DOI":"10.1016\/j.tcs.2022.07.026","volume":"930","author":"G Kortsarz","year":"2022","unstructured":"Kortsarz, G., Nutov, Z., Shalom, E.: Approximating activation edge-cover and facility location problems. Theoret. Comput. Sci. 930, 218\u2013228 (2022)","journal-title":"Theoret. Comput. Sci."},{"issue":"13","key":"10175_CR29","doi-asserted-by":"publisher","first-page":"1424","DOI":"10.1016\/j.dam.2010.04.002","volume":"158","author":"Y Maduel","year":"2010","unstructured":"Maduel, Y., Nutov, Z.: Covering a laminar family by leaf to leaf links. Discret. Appl. Math. 158(13), 1424\u20131432 (2010)","journal-title":"Discret. Appl. Math."},{"key":"10175_CR30","doi-asserted-by":"publisher","first-page":"83","DOI":"10.1016\/S0166-218X(02)00218-4","volume":"126","author":"H Nagamochi","year":"2003","unstructured":"Nagamochi, H.: An approximation for finding a smallest $$2$$-edge connected subgraph containing a specified spanning tree. Discret. Appl. Math. 126, 83\u2013113 (2003)","journal-title":"Discret. Appl. Math."},{"key":"10175_CR31","unstructured":"Nutov, Z.: Structures of Cuts and Cycles in Graphs; Algorithms and Applications. PhD thesis, Technion, Israel Institute of Technology (1997)"},{"key":"10175_CR32","doi-asserted-by":"crossref","unstructured":"Nutov, Z.: Approximating connectivity augmentation problems. ACM Trans. Algorithms. 6(1), 5:1\u20135:19 (2009)","DOI":"10.1145\/1644015.1644020"},{"issue":"1","key":"10175_CR33","doi-asserted-by":"publisher","first-page":"95","DOI":"10.1007\/s00493-014-2773-4","volume":"34","author":"Z Nutov","year":"2014","unstructured":"Nutov, Z.: Approximating minimum-cost edge-covers of crossing biset families. Combinatorica 34(1), 95\u2013114 (2014)","journal-title":"Combinatorica"},{"issue":"2","key":"10175_CR34","doi-asserted-by":"publisher","first-page":"553","DOI":"10.1007\/s00453-020-00765-9","volume":"83","author":"Z Nutov","year":"2021","unstructured":"Nutov, Z.: On the tree augmentation problem. Algorithmica 83(2), 553\u2013575 (2021)","journal-title":"Algorithmica"},{"key":"10175_CR35","doi-asserted-by":"crossref","unstructured":"Nutov, Z.: $$2$$-node-connectivity network design. Theoretical Computer Science. To appear, preliminary version in WAOA 2020: 220\u2013235 (2024)","DOI":"10.1007\/978-3-030-80879-2_15"},{"key":"10175_CR36","doi-asserted-by":"crossref","unstructured":"Traub, V., Zenklusen, R.: A better-than-2 approximation for weighted tree augmentation. In FOCS, pages 1\u201312 (2021)","DOI":"10.1109\/FOCS52979.2021.00010"},{"key":"10175_CR37","doi-asserted-by":"crossref","unstructured":"Traub, V., Zenklusen, R.: Local search for weighted tree augmentation and Steiner tree. In SODA, pages 3253\u20133272 (2022)","DOI":"10.1137\/1.9781611977073.128"},{"key":"10175_CR38","doi-asserted-by":"crossref","unstructured":"Traub, V., Zenklusen, R.: A $$(1.5+\\epsilon )$$-approximation algorithm for weighted connectivity augmentation. In STOC, pages 1820\u20131833, (2023)","DOI":"10.1145\/3564246.3585122"}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-024-10175-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00224-024-10175-x\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-024-10175-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,10,25]],"date-time":"2024-10-25T09:56:17Z","timestamp":1729850177000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00224-024-10175-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,10]]},"references-count":38,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2024,10]]}},"alternative-id":["10175"],"URL":"https:\/\/doi.org\/10.1007\/s00224-024-10175-x","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"value":"1432-4350","type":"print"},{"value":"1433-0490","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,10]]},"assertion":[{"value":"15 March 2024","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"2 October 2024","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}