{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:41:46Z","timestamp":1740109306138,"version":"3.37.3"},"reference-count":20,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2019,7,17]],"date-time":"2019-07-17T00:00:00Z","timestamp":1563321600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2019,7,17]],"date-time":"2019-07-17T00:00:00Z","timestamp":1563321600000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"publisher","award":["270450205"],"award-info":[{"award-number":["270450205"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2020,1]]},"DOI":"10.1007\/s00453-019-00608-2","type":"journal-article","created":{"date-parts":[[2019,7,17]],"date-time":"2019-07-17T09:04:03Z","timestamp":1563354243000},"page":"146-162","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["Computing Vertex-Disjoint Paths in Large Graphs Using MAOs"],"prefix":"10.1007","volume":"82","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-6424-0017","authenticated-orcid":false,"given":"Johanna E.","family":"Prei\u00dfer","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jens M.","family":"Schmidt","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2019,7,17]]},"reference":[{"issue":"5","key":"608_CR1","doi-asserted-by":"publisher","first-page":"251","DOI":"10.1016\/S0020-0190(99)00071-X","volume":"70","author":"SR Arikati","year":"1999","unstructured":"Arikati, S.R., Mehlhorn, K.: A correctness certificate for the Stoer\u2013Wagner min-cut algorithm. Inf. Process. Lett. 70(5), 251\u2013254 (1999)","journal-title":"Inf. Process. Lett."},{"key":"608_CR2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-14279-6","volume-title":"Graph Theory","author":"R Diestel","year":"2010","unstructured":"Diestel, R.: Graph Theory, fourth edn. Springer, Berlin (2010)","edition":"fourth"},{"issue":"4","key":"608_CR3","doi-asserted-by":"publisher","first-page":"507","DOI":"10.1137\/0204043","volume":"4","author":"S Even","year":"1975","unstructured":"Even, S., Tarjan, R.E.: Network flow and testing graph connectivity. SIAM J. Comput. 4(4), 507\u2013518 (1975)","journal-title":"SIAM J. Comput."},{"key":"608_CR4","unstructured":"Frank, A.: On the Edge-Connectivity Algorithm of Nagamochi and Ibaraki. Laboratoire Artemis, IMAG, Universit\u00e9 J. Fourier, Grenoble (Mar 1994)"},{"issue":"1","key":"608_CR5","doi-asserted-by":"publisher","first-page":"197","DOI":"10.1137\/0209016","volume":"9","author":"Z Galil","year":"1980","unstructured":"Galil, Z.: Finding the vertex connectivity of graphs. SIAM J. Comput. 9(1), 197\u2013199 (1980)","journal-title":"SIAM J. Comput."},{"key":"608_CR6","doi-asserted-by":"publisher","first-page":"194","DOI":"10.1006\/jagm.1997.0855","volume":"24","author":"MR Henzinger","year":"1997","unstructured":"Henzinger, M.R.: A static 2-approximation algorithm for vertex connectivity and incremental approximation algorithms for edge and vertex connectivity. J. Algorithms 24, 194\u2013220 (1997)","journal-title":"J. Algorithms"},{"key":"608_CR7","first-page":"81","volume":"5","author":"AV Karzanov","year":"1973","unstructured":"Karzanov, A.V.: O nakhozhdenii maksimal\u2019nogo potoka v setyakh spetsial\u2019nogo vida i nekotorykh prilozheniyakh (in Russian; On finding a maximum flow in a network with special structure and some applications). Matematicheskie Voprosy Upravleniya Proizvodstvom 5, 81\u201394 (1973)","journal-title":"Matematicheskie Voprosy Upravleniya Proizvodstvom"},{"issue":"1","key":"608_CR8","doi-asserted-by":"publisher","first-page":"91","DOI":"10.1007\/BF02122557","volume":"8","author":"N Linial","year":"1988","unstructured":"Linial, N., Lov\u00e1sz, L., Wigderson, A.: Rubber bands, convex embeddings and graph connectivity. Combinatorica 8(1), 91\u2013102 (1988)","journal-title":"Combinatorica"},{"key":"608_CR9","doi-asserted-by":"publisher","first-page":"295","DOI":"10.1007\/BF01350130","volume":"194","author":"W Mader","year":"1971","unstructured":"Mader, W.: Existenz gewisser Konfigurationen in n-ges\u00e4ttigten Graphen und in Graphen gen\u00fcgend gro\u00dfer Kantendichte. Math. Ann. 194, 295\u2013312 (1971)","journal-title":"Math. Ann."},{"key":"608_CR10","doi-asserted-by":"publisher","first-page":"9","DOI":"10.1007\/BF01432512","volume":"205","author":"W Mader","year":"1973","unstructured":"Mader, W.: Grad und lokaler Zusammenhang in endlichen Graphen. Math. Ann. 205, 9\u201311 (1973)","journal-title":"Math. Ann."},{"key":"608_CR11","first-page":"423","volume":"2","author":"W Mader","year":"1996","unstructured":"Mader, W.: On vertices of degree n in minimally n-connected graphs and digraphs. Bolyai Soc. Math. Stud. 2, 423\u2013449 (1996)","journal-title":"Bolyai Soc. Math. Stud."},{"issue":"2","key":"608_CR12","doi-asserted-by":"publisher","first-page":"119","DOI":"10.1016\/j.cosrev.2010.09.009","volume":"5","author":"RM McConnell","year":"2011","unstructured":"McConnell, R.M., Mehlhorn, K., N\u00e4her, S., Schweitzer, P.: Certifying algorithms. Comput. Sci. Rev. 5(2), 119\u2013161 (2011)","journal-title":"Comput. Sci. Rev."},{"key":"608_CR13","doi-asserted-by":"publisher","first-page":"96","DOI":"10.4064\/fm-10-1-96-115","volume":"10","author":"K Menger","year":"1927","unstructured":"Menger, K.: Zur allgemeinen Kurventheorie. Fundam. Math. 10, 96\u2013115 (1927)","journal-title":"Fundam. Math."},{"issue":"16","key":"608_CR14","doi-asserted-by":"publisher","first-page":"2411","DOI":"10.1016\/j.dam.2006.04.008","volume":"154","author":"H Nagamochi","year":"2006","unstructured":"Nagamochi, H.: Sparse connectivity certificates via MA orderings in graphs. Discrete Appl. Math. 154(16), 2411\u20132417 (2006)","journal-title":"Discrete Appl. Math."},{"issue":"1","key":"608_CR15","doi-asserted-by":"publisher","first-page":"54","DOI":"10.1137\/0405004","volume":"5","author":"H Nagamochi","year":"1992","unstructured":"Nagamochi, H., Ibaraki, T.: Computing edge-connectivity in multigraphs and capacitated graphs. SIAM J. Discrete Math. 5(1), 54\u201366 (1992)","journal-title":"SIAM J. Discrete Math."},{"key":"608_CR16","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511721649","volume-title":"Algorithmic Aspects of Graph Connectivity","author":"H Nagamochi","year":"2008","unstructured":"Nagamochi, H., Ibaraki, T.: Algorithmic Aspects of Graph Connectivity. Cambridge University Press, Cambridge (2008)"},{"issue":"2","key":"608_CR17","doi-asserted-by":"publisher","first-page":"494","DOI":"10.1137\/110848311","volume":"42","author":"JM Schmidt","year":"2013","unstructured":"Schmidt, J.M.: Contractions, removals and certifying 3-connectivity in linear time. SIAM J. Comput. 42(2), 494\u2013535 (2013)","journal-title":"SIAM J. Comput."},{"issue":"4","key":"608_CR18","doi-asserted-by":"publisher","first-page":"585","DOI":"10.1145\/263867.263872","volume":"44","author":"M Stoer","year":"1997","unstructured":"Stoer, M., Wagner, F.: A simple min-cut algorithm. J. ACM 44(4), 585\u2013591 (1997)","journal-title":"J. ACM"},{"issue":"3","key":"608_CR19","doi-asserted-by":"publisher","first-page":"566","DOI":"10.1137\/0213035","volume":"13","author":"RE Tarjan","year":"1984","unstructured":"Tarjan, R.E., Yannakakis, M.: Simple linear-time algorithms to test chordality of graphs, test acyclicity of hypergraphs, and selectively reduce acyclic hypergraphs. SIAM J. Comput. 13(3), 566\u2013579 (1984)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"608_CR20","doi-asserted-by":"publisher","first-page":"339","DOI":"10.1090\/S0002-9947-1932-1501641-2","volume":"34","author":"H Whitney","year":"1932","unstructured":"Whitney, H.: Non-separable and planar graphs. Trans. Am. Math. Soc. 34(1), 339\u2013362 (1932)","journal-title":"Trans. Am. Math. Soc."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-019-00608-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-019-00608-2\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-019-00608-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,7,15]],"date-time":"2020-07-15T23:14:48Z","timestamp":1594854888000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-019-00608-2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,7,17]]},"references-count":20,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2020,1]]}},"alternative-id":["608"],"URL":"https:\/\/doi.org\/10.1007\/s00453-019-00608-2","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2019,7,17]]},"assertion":[{"value":"23 October 2018","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"8 July 2019","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"17 July 2019","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}