{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,7]],"date-time":"2025-11-07T13:21:22Z","timestamp":1762521682340},"publisher-location":"Berlin, Heidelberg","reference-count":19,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783662439470"},{"type":"electronic","value":"9783662439487"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2014]]},"DOI":"10.1007\/978-3-662-43948-7_18","type":"book-chapter","created":{"date-parts":[[2014,6,11]],"date-time":"2014-06-11T16:10:36Z","timestamp":1402503036000},"page":"211-222","source":"Crossref","is-referenced-by-count":16,"title":["Shortest Two Disjoint Paths in Polynomial Time"],"prefix":"10.1007","author":[{"given":"Andreas","family":"Bj\u00f6rklund","sequence":"first","affiliation":[]},{"given":"Thore","family":"Husfeldt","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"issue":"1","key":"18_CR1","doi-asserted-by":"publisher","first-page":"280","DOI":"10.1137\/110839229","volume":"43","author":"A. Bj\u00f6rklund","year":"2014","unstructured":"Bj\u00f6rklund, A.: Determinant sums for undirected Hamiltonicity. SIAM J. Comput.\u00a043(1), 280\u2013299 (2014)","journal-title":"SIAM J. Comput."},{"key":"18_CR2","doi-asserted-by":"crossref","unstructured":"Bj\u00f6rklund, A., Husfeldt, T., Taslaman, N.: Shortest cycle through specified elements. In: Proceedings of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2012, Kyoto, Japan, January 17-19, pp. 1747\u20131753. SIAM 2012 (2012)","DOI":"10.1137\/1.9781611973099.139"},{"issue":"2","key":"18_CR3","first-page":"19","volume":"7","author":"E. Colin de Verdi\u00e8re","year":"2011","unstructured":"Colin de Verdi\u00e8re, E., Schrijver, A.: Shortest vertex-disjoint two-face paths in planar graphs. ACM T. Algorithms\u00a07(2), 19 (2011)","journal-title":"ACM T. Algorithms"},{"issue":"4","key":"18_CR4","doi-asserted-by":"publisher","first-page":"241","DOI":"10.6028\/jres.071B.033","volume":"71B","author":"J. Edmonds","year":"1967","unstructured":"Edmonds, J.: Systems of distinct representatives and linear algebra. J. Res. Nat. Bur. Stand.\u00a071B(4), 241\u2013245 (1967)","journal-title":"J. Res. Nat. Bur. Stand."},{"issue":"2","key":"18_CR5","doi-asserted-by":"publisher","first-page":"113","DOI":"10.1016\/S0166-218X(97)00121-2","volume":"85","author":"T. Eilam\u2013Tzoreff","year":"1998","unstructured":"Eilam\u2013Tzoreff, T.: The disjoint shortest paths problem. Discrete Appl. Math.\u00a085(2), 113\u2013138 (1998)","journal-title":"Discrete Appl. Math."},{"key":"18_CR6","doi-asserted-by":"crossref","unstructured":"Fenner, T., Lachish, O., Popa, A.: Min-sum 2-paths problems. In: 11th Workshop on Approximation and Online Algorithms, WAOA 2013, Sophia Antipolis, France, September 5-6 (2013)","DOI":"10.1007\/978-3-319-08001-7_1"},{"issue":"2","key":"18_CR7","doi-asserted-by":"publisher","first-page":"234","DOI":"10.1016\/j.disopt.2010.05.002","volume":"7","author":"Y. Kobayashi","year":"2010","unstructured":"Kobayashi, Y., Sommer, C.: On shortest disjoint paths in planar graphs. Discrete Optim.\u00a07(2), 234\u2013245 (2010)","journal-title":"Discrete Optim."},{"key":"18_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"575","DOI":"10.1007\/978-3-540-70575-8_47","volume-title":"Automata, Languages and Programming","author":"I. Koutis","year":"2008","unstructured":"Koutis, I.: Faster algebraic algorithms for path and packing problems. In: Aceto, L., et al. (eds.) ICALP 2008, Part I. LNCS, vol.\u00a05125, pp. 575\u2013586. Springer, Heidelberg (2008)"},{"issue":"1","key":"18_CR9","doi-asserted-by":"publisher","first-page":"105","DOI":"10.1016\/0166-218X(90)90024-7","volume":"26","author":"C.-L. Li","year":"1990","unstructured":"Li, C.-L., McCormick, S.T., Simchi-Levi, D.: The complexity of finding two disjoint paths with min-max objective function. Discrete Appl. Math.\u00a026(1), 105\u2013115 (1990)","journal-title":"Discrete Appl. Math."},{"issue":"1","key":"18_CR10","doi-asserted-by":"publisher","first-page":"105","DOI":"10.1007\/BF02579206","volume":"7","author":"K. Mulmuley","year":"1987","unstructured":"Mulmuley, K., Vazirani, U.V., Vazirani, V.V.: Matching is as easy as matrix inversion. Combinatorica\u00a07(1), 105\u2013113 (1987)","journal-title":"Combinatorica"},{"key":"18_CR11","doi-asserted-by":"crossref","unstructured":"Ohtsuki, T.: The two disjoint path problem and wire routing design. In: Graph Theory and Algorithms, Proc. 17th Symposium of Research Institute of Electric Communication, Sendai, Japan, October 24-25, 1980, pp. 207\u2013216. Springer (1980)","DOI":"10.1007\/3-540-10704-5_18"},{"key":"18_CR12","doi-asserted-by":"publisher","first-page":"293","DOI":"10.1016\/0012-365X(80)90158-2","volume":"29","author":"P.D. Seymour","year":"1980","unstructured":"Seymour, P.D.: Disjoint paths in graphs. Discrete Math.\u00a029, 293\u2013309 (1980)","journal-title":"Discrete Math."},{"key":"18_CR13","doi-asserted-by":"publisher","first-page":"445","DOI":"10.1145\/322203.322207","volume":"27","author":"Y. Shiloach","year":"1980","unstructured":"Shiloach, Y.: A polynomial solution to the undirected two paths problem. J. ACM\u00a027, 445\u2013456 (1980)","journal-title":"J. ACM"},{"key":"18_CR14","doi-asserted-by":"publisher","first-page":"371","DOI":"10.1016\/S0195-6698(80)80039-4","volume":"1","author":"C. Thomassen","year":"1980","unstructured":"Thomassen, C.: 2-linked graphs. Eur. J. Combin.\u00a01, 371\u2013378 (1980)","journal-title":"Eur. J. Combin."},{"issue":"1","key":"18_CR15","doi-asserted-by":"publisher","first-page":"51","DOI":"10.1007\/s00224-005-1256-9","volume":"39","author":"T. Tholey","year":"2006","unstructured":"Tholey, T.: Solving the 2-disjoint paths problem in nearly linear time. Theory Comput. Syst.\u00a039(1), 51\u201378 (2006)","journal-title":"Theory Comput. Syst."},{"issue":"2","key":"18_CR16","doi-asserted-by":"publisher","first-page":"107","DOI":"10.1112\/jlms\/s1-22.2.107","volume":"22","author":"W.T. Tutte","year":"1947","unstructured":"Tutte, W.T.: The factorization of linear graphs. J. London Math. Soc.\u00a022(2), 107\u2013111 (1947)","journal-title":"J. London Math. Soc."},{"issue":"1","key":"18_CR17","doi-asserted-by":"publisher","first-page":"189","DOI":"10.1016\/0304-3975(79)90044-6","volume":"8","author":"L.G. Valiant","year":"1979","unstructured":"Valiant, L.G.: The complexity of computing the permanent. Theor. Comput. Sci.\u00a08(1), 189\u2013201 (1979)","journal-title":"Theor. Comput. Sci."},{"key":"18_CR18","unstructured":"Wahlstr\u00f6m, M.: Abusing the Tutte matrix: An algebraic instance compression for the K-set-cycle problem. In: 30th International Symposium on Theoretical Aspects of Computer Science, STACS 2013, Kiel, Germany, February 27-March 2. Schloss Dagstuhl \u2013 Leibniz-Zentrum f\u00fcr Informatik LIPIcs, vol.\u00a020, pp. 341\u2013352 (2013)"},{"issue":"6","key":"18_CR19","doi-asserted-by":"publisher","first-page":"315","DOI":"10.1016\/j.ipl.2008.11.004","volume":"109","author":"R. Williams","year":"2009","unstructured":"Williams, R.: Finding paths of length k in O\n                  *(2\n                    k\n                  ) time. Inf. Process. Lett.\u00a0109(6), 315\u2013318 (2009)","journal-title":"Inf. Process. Lett."}],"container-title":["Lecture Notes in Computer Science","Automata, Languages, and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-662-43948-7_18","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,27]],"date-time":"2019-05-27T02:20:47Z","timestamp":1558923647000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-662-43948-7_18"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014]]},"ISBN":["9783662439470","9783662439487"],"references-count":19,"URL":"https:\/\/doi.org\/10.1007\/978-3-662-43948-7_18","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2014]]}}}