{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T19:29:57Z","timestamp":1725564597540},"publisher-location":"Berlin, Heidelberg","reference-count":28,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540212362"},{"type":"electronic","value":"9783540247494"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2004]]},"DOI":"10.1007\/978-3-540-24749-4_31","type":"book-chapter","created":{"date-parts":[[2010,9,8]],"date-time":"2010-09-08T19:01:54Z","timestamp":1283972514000},"page":"350-361","source":"Crossref","is-referenced-by-count":7,"title":["Solving the 2-Disjoint Paths Problem in Nearly Linear Time"],"prefix":"10.1007","author":[{"given":"Torsten","family":"Tholey","sequence":"first","affiliation":[]}],"member":"297","reference":[{"key":"31_CR1","doi-asserted-by":"publisher","first-page":"1321","DOI":"10.1137\/S0097539796312733","volume":"29","author":"A. Aggarwal","year":"2000","unstructured":"Aggarwal, A., Kleinberg, J., Williamson, D.P.: Node-disjoint paths on the mesh and a new trade-off in VLSI layout. SIAM J. Comput.\u00a029, 1321\u20131333 (2000)","journal-title":"SIAM J. Comput."},{"key":"31_CR2","volume-title":"Digraphs: Theory, Algorithms and Applications","author":"J. Bang-Jensen","year":"2001","unstructured":"Bang-Jensen, J., Gutin, G.: Digraphs: Theory, Algorithms and Applications. Springer, London (2001)"},{"key":"31_CR3","doi-asserted-by":"publisher","first-page":"242","DOI":"10.1007\/PL00009195","volume":"20","author":"Y. Dinitz","year":"1998","unstructured":"Dinitz, Y., Westbrook, J.: Maintaining the classes of 4-edge-connectivity in a graph on-line. Algorithmica\u00a020, 242\u2013276 (1998)","journal-title":"Algorithmica"},{"key":"31_CR4","doi-asserted-by":"publisher","first-page":"691","DOI":"10.1137\/0205048","volume":"5","author":"S. Even","year":"1976","unstructured":"Even, S., Itai, A., Shamir, A.: On the complexity of timetable and multicommodity flow problems. SIAM J. Comput.\u00a05, 691\u2013703 (1976)","journal-title":"SIAM J. Comput."},{"key":"31_CR5","doi-asserted-by":"publisher","first-page":"111","DOI":"10.1016\/0304-3975(80)90009-2","volume":"10","author":"S. Fortune","year":"1980","unstructured":"Fortune, S., Hopcroft, J., Wyllie, J.: The directed subgraph homeomorphism problem. Theoret. Comput. Sci.\u00a010, 111\u2013121 (1980)","journal-title":"Theoret. Comput. Sci."},{"key":"31_CR6","doi-asserted-by":"crossref","first-page":"59","DOI":"10.7151\/dmgt.1007","volume":"15","author":"C.P. Gopalakrishnan","year":"1995","unstructured":"Gopalakrishnan, C.P., Pandu Rangan, C.: Edge-disjoint paths in permutation graphs. Discuss. Math. Graph Theory\u00a015, 59\u201372 (1995)","journal-title":"Discuss. Math. Graph Theory"},{"key":"31_CR7","unstructured":"Gustedt, J.: The general two-path problem in time O(m log n) (extended abstract), Report No. 394\/1994, TU Berlin, FB Mathematik (1994)"},{"key":"31_CR8","unstructured":"Jungnickel, D.: Graphen, Netzwerke und Algorithmen, B. I. Wissenschaftsverlag, Mannheim (1994)"},{"key":"31_CR9","doi-asserted-by":"crossref","unstructured":"Kanevsky, A., Tamassia, R., Di Battista, G., Chen, J.: On-line maintenance of the four-connected components of a graph. In: Proc. 32nd Annual IEEE Symposium on Foundations of Computer Science (FOCS 1991), pp. 793\u2013801 (1991)","DOI":"10.1109\/SFCS.1991.185451"},{"key":"31_CR10","doi-asserted-by":"crossref","first-page":"45","DOI":"10.1002\/net.1975.5.1.45","volume":"5","author":"R.M. Karp","year":"1975","unstructured":"Karp, R.M.: On the computational complexity of combinatorial problems. Networks\u00a05, 45\u201368 (1975)","journal-title":"Networks"},{"key":"31_CR11","doi-asserted-by":"publisher","first-page":"486","DOI":"10.1137\/0221032","volume":"21","author":"S. Khuller","year":"1992","unstructured":"Khuller, S., Mitchell, S.G., Vazirani, V.V.: Processor efficient parallel algorithms for the two disjoint paths problem and for finding a Kuratowski homeomorph. SIAM J. Comput.\u00a021, 486\u2013506 (1992)","journal-title":"SIAM J. Comput."},{"key":"31_CR12","doi-asserted-by":"publisher","first-page":"147","DOI":"10.1016\/0166-218X(93)90035-M","volume":"41","author":"E. Korach","year":"1993","unstructured":"Korach, E., Tal, A.: General vertex disjoint paths in series-parallel graphs. Discrete Appl. Math.\u00a041, 147\u2013164 (1993)","journal-title":"Discrete Appl. Math."},{"key":"31_CR13","unstructured":"Lucchesi, C.L., Giglio, M.C.M.T.: On the irrelevance of edge orientations on the acyclic directed two disjoint paths problem, IC Technical Report DCC-92-03, Universidade Estadual de Campinas, Instituto de Computa\u00e7\u00e3o (1992)"},{"key":"31_CR14","doi-asserted-by":"publisher","first-page":"31","DOI":"10.1145\/1061425.1061430","volume":"5","author":"J.F. Lynch","year":"1975","unstructured":"Lynch, J.F.: The equivalence of theorem proving and the interconnection problem. (ACM) SIGDA Newsletter\u00a05, 31\u201336 (1975)","journal-title":"(ACM) SIGDA Newsletter"},{"key":"31_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"207","DOI":"10.1007\/3-540-10704-5_18","volume-title":"Graph Theory and Algorithms","author":"T. Ohtsuki","year":"1981","unstructured":"Ohtsuki, T.: The two disjoint path problem and wire routing design. In: Saito, N., Nishizeki, T. (eds.) Graph Theory and Algorithms. LNCS, vol.\u00a0108, pp. 207\u2013216. Springer, Heidelberg (1981)"},{"key":"31_CR16","doi-asserted-by":"publisher","first-page":"365","DOI":"10.1142\/S0129054100000247","volume":"11","author":"L. Perkovi\u0107","year":"2000","unstructured":"Perkovi\u0107, L., Reed, B.: An improved algorithm for finding tree decompositions of small width. International Journal of Foundations of Computer Science (IJFCS)\u00a011, 365\u2013372 (2000)","journal-title":"International Journal of Foundations of Computer Science (IJFCS)"},{"key":"31_CR17","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/322047.322048","volume":"25","author":"Y. Perl","year":"1978","unstructured":"Perl, Y., Shiloach, Y.: Finding two disjoint paths between two pairs of vertices in a graph. J. ACM\u00a025, 1\u20139 (1978)","journal-title":"J. ACM"},{"key":"31_CR18","doi-asserted-by":"publisher","first-page":"65","DOI":"10.1006\/jctb.1995.1006","volume":"63","author":"N. Robertson","year":"1995","unstructured":"Robertson, N., Seymour, P.D.: Graph minors. XIII. The disjoint paths problem. J. Comb. Theory, Ser. B\u00a063, 65\u2013110 (1995)","journal-title":"J. Comb. Theory, Ser. B"},{"key":"31_CR19","unstructured":"Scheffler, P.: A practical linear time algorithm for disjoint paths in graphs with bounded tree-width, Report No. 396\/1994, TU Berlin, FB Mathematik (1994)"},{"key":"31_CR20","first-page":"257","volume":"6","author":"A. Schrijver","year":"1993","unstructured":"Schrijver, A.: A group-theoretical approach to disjoint paths in directed graphs. CWI Quarterly\u00a06, 257\u2013266 (1993)","journal-title":"CWI Quarterly"},{"key":"31_CR21","volume-title":"Combinatorial optimization \u2013 Polyhedra and Efficiency","author":"A. Schrijver","year":"2002","unstructured":"Schrijver, A.: Combinatorial optimization \u2013 Polyhedra and Efficiency, vol.\u00a0C. Springer, Berlin (2002)"},{"key":"31_CR22","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"250","DOI":"10.1007\/3-540-52282-4_48","volume-title":"STACS 90","author":"A. Schwill","year":"1990","unstructured":"Schwill, A.: Nonblocking graphs: greedy algorithms to compute disjoint paths. In: Choffrut, C., Lengauer, T. (eds.) STACS 1990. LNCS, vol.\u00a0415, pp. 250\u2013262. Springer, Heidelberg (1990)"},{"key":"31_CR23","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":"31_CR24","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":"31_CR25","doi-asserted-by":"publisher","first-page":"325","DOI":"10.1002\/net.3230140209","volume":"14","author":"J.W. Suurballe","year":"1984","unstructured":"Suurballe, J.W., Tarjan, R.E.: A quick method for finding shortest pairs of disjoint paths. Networks\u00a014, 325\u2013336 (1984)","journal-title":"Networks"},{"key":"31_CR26","doi-asserted-by":"crossref","first-page":"371","DOI":"10.1016\/S0195-6698(80)80039-4","volume":"1","author":"C. Thomassen","year":"1980","unstructured":"Thomassen, C.: 2-linked graphs. Europ. J. Combinatorics\u00a01, 371\u2013378 (1980)","journal-title":"Europ. J. Combinatorics"},{"key":"31_CR27","doi-asserted-by":"publisher","first-page":"231","DOI":"10.1215\/S0012-7094-68-03523-0","volume":"35","author":"M.E. Watkins","year":"1968","unstructured":"Watkins, M.E.: On the existence of certain disjoint arcs in graphs. Duke Math. J.\u00a035, 231\u2013246 (1968)","journal-title":"Duke Math. J."},{"key":"31_CR28","doi-asserted-by":"publisher","first-page":"681","DOI":"10.1145\/1634.322451","volume":"31","author":"S.G. Williamson","year":"1984","unstructured":"Williamson, S.G.: Depth-first search and Kuratowski subgraphs. J. ACM\u00a031, 681\u2013693 (1984)","journal-title":"J. ACM"}],"container-title":["Lecture Notes in Computer Science","STACS 2004"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-24749-4_31","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,1,28]],"date-time":"2019-01-28T22:58:07Z","timestamp":1548716287000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-24749-4_31"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2004]]},"ISBN":["9783540212362","9783540247494"],"references-count":28,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-24749-4_31","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2004]]}}}