{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T16:02:52Z","timestamp":1725552172254},"publisher-location":"Berlin, Heidelberg","reference-count":17,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540310006"},{"type":"electronic","value":"9783540314684"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2005]]},"DOI":"10.1007\/11604686_28","type":"book-chapter","created":{"date-parts":[[2005,12,5]],"date-time":"2005-12-05T15:02:01Z","timestamp":1133794921000},"page":"319-330","source":"Crossref","is-referenced-by-count":4,"title":["Finding Disjoint Paths on Directed Acyclic Graphs"],"prefix":"10.1007","author":[{"given":"Torsten","family":"Tholey","sequence":"first","affiliation":[]}],"member":"297","reference":[{"key":"28_CR1","doi-asserted-by":"publisher","first-page":"302","DOI":"10.1007\/PL00009264","volume":"23","author":"G. Battista Di","year":"1999","unstructured":"Di Battista, G., Tamassia, R., Vismara, L.: Output-sensitive reporting of disjoint paths. Algorithmica\u00a023, 302\u2013340 (1999)","journal-title":"Algorithmica"},{"key":"28_CR2","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":"28_CR3","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":"28_CR4","doi-asserted-by":"publisher","first-page":"723","DOI":"10.1145\/502090.502095","volume":"48","author":"J. Holm","year":"2001","unstructured":"Holm, J., de Lichtenberg, K., Thorup, M.: Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity. J. ACM\u00a048, 723\u2013760 (2001)","journal-title":"J. ACM"},{"key":"28_CR5","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":"28_CR6","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":"28_CR7","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\u2013371 (2000)","journal-title":"International Journal of Foundations of Computer Science (IJFCS)"},{"key":"28_CR8","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":"28_CR9","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":"28_CR10","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":"28_CR11","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":"28_CR12","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":"28_CR13","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":"28_CR14","doi-asserted-by":"publisher","first-page":"245","DOI":"10.1145\/62.2160","volume":"31","author":"R.E. Tarjan","year":"1984","unstructured":"Tarjan, R.E., van Leeuwen, J.: Worst-case analysis of set union algorithms. J. ACM\u00a031, 245\u2013281 (1984)","journal-title":"J. ACM"},{"key":"28_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"350","DOI":"10.1007\/978-3-540-24749-4_31","volume-title":"STACS 2004","author":"T. Tholey","year":"2004","unstructured":"Tholey, T.: Solving the 2-disjoint paths problem in nearly linear time. In: Diekert, V., Habib, M. (eds.) STACS 2004. LNCS, vol.\u00a02996, pp. 350\u2013361. Springer, Heidelberg (2004)"},{"key":"28_CR16","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":"28_CR17","doi-asserted-by":"publisher","first-page":"73","DOI":"10.1016\/S0012-365X(85)80022-4","volume":"55","author":"C. Thomassen","year":"1985","unstructured":"Thomassen, C.: The 2-linkage problem for acyclic digraphs. Discrete Math.\u00a055, 73\u201387 (1985)","journal-title":"Discrete Math."}],"container-title":["Lecture Notes in Computer Science","Graph-Theoretic Concepts in Computer Science"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11604686_28.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T07:04:25Z","timestamp":1619507065000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11604686_28"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005]]},"ISBN":["9783540310006","9783540314684"],"references-count":17,"URL":"https:\/\/doi.org\/10.1007\/11604686_28","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2005]]}}}