{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,23]],"date-time":"2026-07-23T23:51:05Z","timestamp":1784850665052,"version":"3.55.0"},"reference-count":22,"publisher":"Springer Science and Business Media LLC","issue":"1-2","license":[{"start":{"date-parts":[[2023,4,26]],"date-time":"2023-04-26T00:00:00Z","timestamp":1682467200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2023,4,26]],"date-time":"2023-04-26T00:00:00Z","timestamp":1682467200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-1918656"],"award-info":[{"award-number":["CCF-1918656"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000038","name":"Natural Sciences and Engineering Research Council of Canada","doi-asserted-by":"publisher","award":["RGPIN-2019-04197"],"award-info":[{"award-number":["RGPIN-2019-04197"]}],"id":[{"id":"10.13039\/501100000038","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000038","name":"Natural Sciences and Engineering Research Council of Canada","doi-asserted-by":"publisher","award":["327620-09"],"award-info":[{"award-number":["327620-09"]}],"id":[{"id":"10.13039\/501100000038","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Math. Program."],"published-print":{"date-parts":[[2024,3]]},"DOI":"10.1007\/s10107-023-01961-5","type":"journal-article","created":{"date-parts":[[2023,4,26]],"date-time":"2023-04-26T14:05:42Z","timestamp":1682517942000},"page":"493-516","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":10,"title":["Approximation algorithms for flexible graph connectivity"],"prefix":"10.1007","volume":"204","author":[{"given":"Sylvia","family":"Boyd","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0316-7650","authenticated-orcid":false,"given":"Joseph","family":"Cheriyan","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Arash","family":"Haddadan","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1575-9648","authenticated-orcid":false,"given":"Sharat","family":"Ibrahimpur","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2023,4,26]]},"reference":[{"key":"1961_CR1","doi-asserted-by":"crossref","unstructured":"Adjiashvili, D., Hommelsheim, F., M\u00fchlenthaler, M.: Flexible graph connectivity. In: Proceedings of the 21st Integer Programming and Combinatorial Optimization Conference, Volume 12125 of Lecture Notes in Computer Science, pp. 13\u201326 (2020)","DOI":"10.1007\/978-3-030-45771-6_2"},{"key":"1961_CR2","doi-asserted-by":"crossref","unstructured":"Adjiashvili, D., Hommelsheim, F., M\u00fchlenthaler, M.: Flexible graph connectivity. Math. Program. 1\u201333 (2021)","DOI":"10.1007\/s10107-021-01664-9"},{"issue":"2","key":"1961_CR3","doi-asserted-by":"publisher","first-page":"493","DOI":"10.1007\/s00453-013-9862-4","volume":"72","author":"D Chakrabarty","year":"2015","unstructured":"Chakrabarty, D., Chekuri, C., Khanna, S., Korula, N.: Approximability of capacitated network design. Algorithmica 72(2), 493\u2013514 (2015)","journal-title":"Algorithmica"},{"issue":"1","key":"1961_CR4","doi-asserted-by":"publisher","first-page":"51","DOI":"10.1006\/jagm.1999.1039","volume":"33","author":"L Fleischer","year":"1999","unstructured":"Fleischer, L.: Building chain and cactus representations of all minimum cuts from Hao\u2013Orlin in the same asymptotic run time. J. Algorithms 33(1), 51\u201372 (1999)","journal-title":"J. Algorithms"},{"issue":"1","key":"1961_CR5","doi-asserted-by":"publisher","first-page":"65","DOI":"10.1007\/BF01202790","volume":"13","author":"A Frank","year":"1993","unstructured":"Frank, A.: Conservative weightings and ear-decompositions of graphs. Combinatorica 13(1), 65\u201381 (1993)","journal-title":"Combinatorica"},{"issue":"1","key":"1961_CR6","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1137\/S0895480102405476","volume":"18","author":"HN Gabow","year":"2004","unstructured":"Gabow, H.N.: An ear decomposition approach to approximating the smallest 3-edge connected spanning subgraph of a multigraph. SIAM J. Discrete Math. 18(1), 41\u201370 (2004)","journal-title":"SIAM J. Discrete Math."},{"issue":"1","key":"1961_CR7","doi-asserted-by":"publisher","first-page":"61","DOI":"10.1137\/080732572","volume":"41","author":"HN Gabow","year":"2012","unstructured":"Gabow, H.N., Gallagher, S.: Iterated rounding algorithms for the smallest $${k}$$-edge connected spanning subgraph. SIAM J. Comput. 41(1), 61\u2013103 (2012)","journal-title":"SIAM J. Comput."},{"issue":"4","key":"1961_CR8","doi-asserted-by":"publisher","first-page":"345","DOI":"10.1002\/net.20289","volume":"53","author":"HN Gabow","year":"2009","unstructured":"Gabow, H.N., Goemans, M.X., Tardos, \u00c9., Williamson, D.P.: Approximating the smallest k-edge connected spanning subgraph by LP-rounding. Networks 53(4), 345\u2013357 (2009)","journal-title":"Networks"},{"key":"1961_CR9","unstructured":"Goemans, M.X., Goldberg, A.V., Plotkin, S.A., Shmoys, D.B., Tardos, \u00c9., Williamson, D.P.: Improved approximation algorithms for network design problems. In: Proceedings of the 5th Symposium on Discrete Algorithms, pp. 223\u2013232 (1994)"},{"key":"1961_CR10","first-page":"144","volume-title":"The Primal\u2013Dual Method for Approximation Algorithms and Its Application to Network Design Problems, Chapter 4","author":"MX Goemans","year":"1997","unstructured":"Goemans, M.X., Williamson, D.P.: The Primal\u2013Dual Method for Approximation Algorithms and Its Application to Network Design Problems, Chapter 4, pp. 144\u2013191. PWS Publishing Company, Boston (1997)"},{"issue":"4","key":"1961_CR11","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/3341599","volume":"15","author":"C Hunkenschr\u00f6der","year":"2019","unstructured":"Hunkenschr\u00f6der, C., Vempala, S., Vetta, A.: A 4\/3-approximation algorithm for the minimum 2-edge connected subgraph problem. ACM Trans. Algorithms 15(4), 1\u201328 (2019)","journal-title":"ACM Trans. Algorithms"},{"issue":"1","key":"1961_CR12","doi-asserted-by":"publisher","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":"1961_CR13","unstructured":"Karger, D.R.: Global min-cuts in $${\\cal{R}}{\\cal{N}}{\\cal{C}}$$, and other ramifications of a simple min-cut algorithm. In: Proceedings of the 4th Symposium on Discrete Algorithms, pp. 21\u201330 (1993)"},{"issue":"2","key":"1961_CR14","doi-asserted-by":"publisher","first-page":"214","DOI":"10.1145\/174652.174654","volume":"41","author":"S Khuller","year":"1994","unstructured":"Khuller, S., Vishkin, U.: Biconnectivity approximations and graph carvings. J. ACM 41(2), 214\u2013235 (1994)","journal-title":"J. ACM"},{"issue":"1","key":"1961_CR15","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1287\/trsc.18.1.1","volume":"18","author":"TL Magnanti","year":"1984","unstructured":"Magnanti, T.L., Wong, R.T.: Network design and transportation planning: models and algorithms. Transp. Sci. 18(1), 1\u201355 (1984)","journal-title":"Transp. Sci."},{"issue":"3","key":"1961_CR16","doi-asserted-by":"publisher","first-page":"469","DOI":"10.1137\/S0895480194271323","volume":"10","author":"H Nagamochi","year":"1997","unstructured":"Nagamochi, H., Nishimura, K., Ibaraki, T.: Computing all small cuts in an undirected network. SIAM J. Discrete Math. 10(3), 469\u2013481 (1997)","journal-title":"SIAM J. Discrete Math."},{"key":"1961_CR17","doi-asserted-by":"crossref","unstructured":"Rozenshtein, P., Gionis, A., Prakash, B.A., Vreeken, J.: Reconstructing an epidemic over time. In: Proceedings of the 22nd International Conference on Knowledge Discovery and Data Mining, pp. 1835\u20131844 (2016)","DOI":"10.1145\/2939672.2939865"},{"key":"1961_CR18","unstructured":"Schrijver, A.: Combinatorial Optimization: Polyhedra and Efficiency. Algorithms and Combinatorics, vol. 24. Springer-Verlag, Berlin Heidelberg (2003)"},{"issue":"5","key":"1961_CR19","doi-asserted-by":"publisher","first-page":"597","DOI":"10.1007\/s00493-014-2960-3","volume":"34","author":"A Seb\u00f6","year":"2014","unstructured":"Seb\u00f6, A., Vygen, J.: Shorter tours by nicer ears: 7\/5-approximation for the graph-TSP, 3\/2 for the path version, and 4\/3 for two-edge-connected subgraphs. Combinatorica 34(5), 597\u2013629 (2014)","journal-title":"Combinatorica"},{"key":"1961_CR20","first-page":"234","volume-title":"Planning for Disruptions in Supply Chain Networks","author":"LV Snyder","year":"2014","unstructured":"Snyder, L.V., Scaparra, M.P., Daskin, M.S., Church, R.L.: Planning for Disruptions in Supply Chain Networks, pp. 234\u2013257. Institute for Operations Research and the Management Sciences, Hanover (2014)"},{"key":"1961_CR21","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-04565-7","volume-title":"Approximation Algorithms","author":"VV Vazirani","year":"2003","unstructured":"Vazirani, V.V.: Approximation Algorithms. Springer, Berlin (2003)"},{"issue":"3","key":"1961_CR22","doi-asserted-by":"publisher","first-page":"435","DOI":"10.1007\/BF01299747","volume":"15","author":"DP Williamson","year":"1995","unstructured":"Williamson, D.P., Goemans, M.X., Mihail, M., Vazirani, V.V.: A primal\u2013dual approximation algorithm for generalized Steiner network problems. Combinatorica 15(3), 435\u2013454 (1995)","journal-title":"Combinatorica"}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-023-01961-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10107-023-01961-5\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-023-01961-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,2,15]],"date-time":"2024-02-15T21:32:02Z","timestamp":1708032722000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10107-023-01961-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,4,26]]},"references-count":22,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2024,3]]}},"alternative-id":["1961"],"URL":"https:\/\/doi.org\/10.1007\/s10107-023-01961-5","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"value":"0025-5610","type":"print"},{"value":"1436-4646","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,4,26]]},"assertion":[{"value":"30 December 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"27 March 2023","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"26 April 2023","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}