{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,7]],"date-time":"2026-02-07T11:23:48Z","timestamp":1770463428167,"version":"3.49.0"},"reference-count":27,"publisher":"Springer Science and Business Media LLC","issue":"9","license":[{"start":{"date-parts":[[2022,5,20]],"date-time":"2022-05-20T00:00:00Z","timestamp":1653004800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2022,5,20]],"date-time":"2022-05-20T00:00:00Z","timestamp":1653004800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100009328","name":"Planning and Budgeting Committee of the Council for Higher Education of Israel","doi-asserted-by":"publisher","award":["5101479000)."],"award-info":[{"award-number":["5101479000)."]}],"id":[{"id":"10.13039\/501100009328","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100010663","name":"H2020 European Research Council","doi-asserted-by":"publisher","award":["819416"],"award-info":[{"award-number":["819416"]}],"id":[{"id":"10.13039\/100010663","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2022,9]]},"DOI":"10.1007\/s00453-022-00959-3","type":"journal-article","created":{"date-parts":[[2022,5,20]],"date-time":"2022-05-20T22:05:52Z","timestamp":1653084352000},"page":"2622-2641","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Fast Exact Algorithms for Survivable Network Design with Uniform Requirements"],"prefix":"10.1007","volume":"84","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-0656-7572","authenticated-orcid":false,"given":"Akanksha","family":"Agrawal","sequence":"first","affiliation":[]},{"given":"Pranabendu","family":"Misra","sequence":"additional","affiliation":[]},{"given":"Fahad","family":"Panolan","sequence":"additional","affiliation":[]},{"given":"Saket","family":"Saurabh","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2022,5,20]]},"reference":[{"key":"959_CR1","volume-title":"Digraphs: theory, algorithms and applications","author":"J Bang-Jensen","year":"2008","unstructured":"Bang-Jensen, J., Gutin, G.Z.: Digraphs: theory, algorithms and applications. Springer Science & Business Media, Berlin (2008)"},{"key":"959_CR2","doi-asserted-by":"crossref","unstructured":"Basavaraju, M., Fomin, F.V., Golovach, P., Misra, P., Ramanujan, M., Saurabh, S.: Parameterized algorithms to preserve connectivity. In: Automata, Languages, and Programming, pp. 800\u2013811. Springer (2014)","DOI":"10.1007\/978-3-662-43948-7_66"},{"issue":"1","key":"959_CR3","doi-asserted-by":"publisher","first-page":"61","DOI":"10.1145\/321105.321111","volume":"9","author":"R Bellman","year":"1962","unstructured":"Bellman, R.: Dynamic programming treatment of the travelling salesman problem. J. ACM (JACM) 9(1), 61\u201363 (1962)","journal-title":"J. ACM (JACM)"},{"key":"959_CR4","doi-asserted-by":"crossref","unstructured":"Berman, P., Dasgupta, B., Karpinski, M.: Approximating transitive reductions for directed networks. In: Proceedings of the 11th International Symposium on Algorithms and Data Structures. pp. 74\u201385. Springer-Verlag (2009)","DOI":"10.1007\/978-3-642-03367-4_7"},{"issue":"1","key":"959_CR5","doi-asserted-by":"publisher","first-page":"280","DOI":"10.1137\/110839229","volume":"43","author":"A Bjorklund","year":"2014","unstructured":"Bjorklund, A.: Determinant sums for undirected hamiltonicity. SIAM J. Comput. 43(1), 280\u2013299 (2014)","journal-title":"SIAM J. Comput."},{"issue":"2","key":"959_CR6","doi-asserted-by":"publisher","first-page":"528","DOI":"10.1137\/S009753979833920X","volume":"30","author":"J Cheriyan","year":"2000","unstructured":"Cheriyan, J., Thurimella, R.: Approximating minimum-size k-connected spanning subgraphs via matching. SIAM J. Comput. 30(2), 528\u2013560 (2000)","journal-title":"SIAM J. Comput."},{"key":"959_CR7","doi-asserted-by":"crossref","unstructured":"Cygan, M., Fomin, F.V., Golovnev, A., Kulikov, A.S., Mihajlin, I., Pachocki, J., Socala, A.: Tight bounds for graph homomorphism and subgraph isomorphism. In: Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016, Arlington, VA, USA, January 10\u201312, 2016. pp. 1643\u20131649 (2016)","DOI":"10.1137\/1.9781611974331.ch112"},{"key":"959_CR8","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-21275-3","volume-title":"Parameterized Algorithms","author":"M Cygan","year":"2015","unstructured":"Cygan, M., Fomin, F.V., Kowalik, L., Lokshtanov, D., Marx, D., Pilipczuk, M., Pilipczuk, M., Saurabh, S.: Parameterized Algorithms. Springer, Berlin (2015)"},{"key":"959_CR9","doi-asserted-by":"crossref","unstructured":"Cygan, M., Kratsch, S., Nederlof, J.: Fast hamiltonicity checking via bases of perfect matchings. In: Proceedings of the forty-fifth annual ACM Symposium on Theory of Computing. pp. 301\u2013310. ACM (2013)","DOI":"10.1145\/2488608.2488646"},{"key":"959_CR10","doi-asserted-by":"crossref","unstructured":"Fomin, F.V., Lokshtanov, D., Panolan, F., Saurabh, S.: Efficient computation of representative families with applications in parameterized and exact algorithms. J. ACM 63(4), 29:1\u201329:60 (Sep 2016), http:\/\/doi.acm.org\/10.1145\/2886094","DOI":"10.1145\/2886094"},{"issue":"1","key":"959_CR11","doi-asserted-by":"publisher","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."},{"key":"959_CR12","doi-asserted-by":"crossref","unstructured":"Frank, H., Chou, W.: Connectivity considerations in the design of survivable networks. Circuit Theory, IEEE Transactions on 17(4), 486\u2013D490 (1970)","DOI":"10.1109\/TCT.1970.1083185"},{"issue":"2","key":"959_CR13","doi-asserted-by":"publisher","first-page":"259","DOI":"10.1006\/jcss.1995.1022","volume":"50","author":"HN Gabow","year":"1995","unstructured":"Gabow, H.N.: A matroid approach to finding edge connectivity and packing arborescences. J. Comput. Syst. Sci. 50(2), 259\u2013273 (1995)","journal-title":"J. Comput. Syst. Sci."},{"issue":"3","key":"959_CR14","doi-asserted-by":"publisher","first-page":"552","DOI":"10.1137\/0217034","volume":"17","author":"D Gusfield","year":"1988","unstructured":"Gusfield, D.: A graph theoretic approach to statistical data security. SIAM J. Comput. 17(3), 552\u2013571 (1988)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"959_CR15","doi-asserted-by":"publisher","first-page":"196","DOI":"10.1137\/0110015","volume":"10","author":"M Held","year":"1962","unstructured":"Held, M., Karp, R.M.: A dynamic programming approach to sequencing problems. J. Soc. Ind. Appl. Math. 10(1), 196\u2013210 (1962)","journal-title":"J. Soc. Ind. Appl. Math."},{"issue":"5","key":"959_CR16","doi-asserted-by":"publisher","first-page":"541","DOI":"10.1109\/TR.1986.4335542","volume":"35","author":"S Jain","year":"1986","unstructured":"Jain, S., Gopal, K.: On network augmentation. Reliab. IEEE Trans. 35(5), 541\u2013543 (1986)","journal-title":"Reliab. IEEE Trans."},{"issue":"1","key":"959_CR17","doi-asserted-by":"publisher","first-page":"87","DOI":"10.1137\/S0895480193243274","volume":"9","author":"MY Kao","year":"1996","unstructured":"Kao, M.Y.: Data security equals graph connectivity. SIAM J. Discrete Math. 9(1), 87\u2013100 (1996)","journal-title":"SIAM J. Discrete Math."},{"key":"959_CR18","first-page":"2","volume":"2","author":"S Khuller","year":"1997","unstructured":"Khuller, S.: Approximation algorithms for finding highly connected subgraphs. Vertex 2, 2 (1997)","journal-title":"Vertex"},{"issue":"2","key":"959_CR19","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 (JACM) 41(2), 214\u2013235 (1994)","journal-title":"J. ACM (JACM)"},{"key":"959_CR20","unstructured":"Kortsarz, G., Nutov, Z.: Approximating minimum cost connectivity problems. In: Dagstuhl Seminar Proceedings. Schloss Dagstuhl-Leibniz-Zentrum f\u00fcr Informatik (2010)"},{"key":"959_CR21","doi-asserted-by":"crossref","unstructured":"Marx, D.: A parameterized view on matroid optimization problems. Theor. Comput. Sci. 410(44), 4471\u20134479 (2009), http:\/\/dx.doi.org\/10.1016\/j.tcs.2009.07.027","DOI":"10.1016\/j.tcs.2009.07.027"},{"issue":"4","key":"959_CR22","first-page":"27","volume":"11","author":"D Marx","year":"2015","unstructured":"Marx, D., V\u00e9gh, L.A.: Fixed-parameter algorithms for minimum-cost edge-connectivity augmentation. ACM Trans. Algorithms (TALG) 11(4), 27 (2015)","journal-title":"ACM Trans. Algorithms (TALG)"},{"issue":"3","key":"959_CR23","doi-asserted-by":"publisher","first-page":"455","DOI":"10.1145\/321526.321534","volume":"16","author":"DM Moyles","year":"1969","unstructured":"Moyles, D.M., Thompson, G.L.: An algorithm for finding a minimum equivalent graph of a digraph. J. ACM (JACM) 16(3), 455\u2013460 (1969)","journal-title":"J. ACM (JACM)"},{"key":"959_CR24","volume-title":"Matroid Theory","author":"JG Oxley","year":"2006","unstructured":"Oxley, J.G.: Matroid Theory, vol. 3. Oxford University Press, USA (2006)"},{"key":"959_CR25","volume-title":"Combinatorial optimization: polyhedra and efficiency","author":"A Schrijver","year":"2003","unstructured":"Schrijver, A.: Combinatorial optimization: polyhedra and efficiency. Springer Science & Business Media, Berlin (2003)"},{"key":"959_CR26","doi-asserted-by":"crossref","unstructured":"Watanabe, T., Narita, T., Nakamura, A.: 3-edge-connectivity augmentation problems. In: Circuits and Systems, 1989., IEEE International Symposium on. pp. 335\u2013338. IEEE (1989)","DOI":"10.1109\/ISCAS.1989.100359"},{"key":"959_CR27","doi-asserted-by":"crossref","unstructured":"Williams, V.V.: Multiplying matrices faster than Coppersmith-Winograd. In: ACM symposium on Theory of computing. pp. 887\u2013898 (2012)","DOI":"10.1145\/2213977.2214056"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-022-00959-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-022-00959-3\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-022-00959-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,9,25]],"date-time":"2024-09-25T17:44:40Z","timestamp":1727286280000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-022-00959-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,5,20]]},"references-count":27,"journal-issue":{"issue":"9","published-print":{"date-parts":[[2022,9]]}},"alternative-id":["959"],"URL":"https:\/\/doi.org\/10.1007\/s00453-022-00959-3","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,5,20]]},"assertion":[{"value":"10 December 2019","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"1 March 2022","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"20 May 2022","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}