{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T18:17:17Z","timestamp":1725560237558},"publisher-location":"Berlin, Heidelberg","reference-count":19,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540200642"},{"type":"electronic","value":"9783540396581"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2003]]},"DOI":"10.1007\/978-3-540-39658-1_44","type":"book-chapter","created":{"date-parts":[[2010,7,22]],"date-time":"2010-07-22T23:24:30Z","timestamp":1279841070000},"page":"482-493","source":"Crossref","is-referenced-by-count":13,"title":["Parameterized Tractability of Edge-Disjoint Paths on Directed Acyclic Graphs"],"prefix":"10.1007","author":[{"given":"Aleksandrs","family":"Slivkins","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"44_CR1","doi-asserted-by":"crossref","unstructured":"Baier, G., K\u00f6hler, E., Skutella, M.: On the k-Splittable Flow Problem. In: Proc. 10th Annual European Symposium on Algorithms (2002)","DOI":"10.1007\/3-540-45749-6_13"},{"key":"44_CR2","doi-asserted-by":"crossref","unstructured":"Dinitz, Y., Garg, N., Goemans, M.: On the Single-Source Unsplittable Flow Problem. In: Proc. 39th Annual Symposium on Foundations of Computer Science (1998)","DOI":"10.1109\/SFCS.1998.743461"},{"key":"44_CR3","unstructured":"Downey, R., Estivill-Castro, V., Fellows, M., Prieto, E., Rosamund, F.: Cutting Up is Hard to Do: the Parameterized Complexity of k-Cut and Related Problems. In: Computing: The Australasian Theory Symposium (2003)"},{"key":"44_CR4","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-0515-9","volume-title":"Parameterized Complexity","author":"R.G. Downey","year":"1999","unstructured":"Downey, R.G., Fellows, M.R.: Parameterized Complexity. Springer, Heidelberg (1999)"},{"key":"44_CR5","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. Computing\u00a05, 691\u2013703 (1976)","journal-title":"SIAM J. Computing"},{"key":"44_CR6","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. Theoretical Computer Science\u00a010, 111\u2013121 (1980)","journal-title":"Theoretical Computer Science"},{"volume-title":"Paths, Flows andVLSI-Layouts","year":"1990","key":"44_CR7","unstructured":"Korte, B., Lov\u00e1sz, L., Pr\u00f6mel, H.-J., Schrijver, A. (eds.): Paths, Flows andVLSI-Layouts. Springer, Heidelberg (1990)"},{"key":"44_CR8","doi-asserted-by":"crossref","first-page":"85","DOI":"10.1007\/978-1-4684-2001-2_9","volume-title":"Complexity of Computer Computations","author":"R.M. Karp","year":"1972","unstructured":"Karp, R.M.: Reducibility among combinatorial problems. In: Miller, R.E., Thatcher, J.W. (eds.) Complexity of Computer Computations, pp. 85\u2013103. Plenum Press, NewYork (1972)"},{"key":"44_CR9","doi-asserted-by":"crossref","unstructured":"Kleinberg, J.: Single-source unsplittable flow. In: Proc. 37th Annual Symposium on Foundations of Computer Science (1996)","DOI":"10.1109\/SFCS.1996.548465"},{"key":"44_CR10","doi-asserted-by":"crossref","unstructured":"Kleinberg, J.: Decision algorithms for unsplittable flow and the half-disjoint paths problem. In: Proc. 30th Annual ACM Symposium on the Theory of Computing (1998)","DOI":"10.1145\/276698.276867"},{"key":"44_CR11","unstructured":"Kleinberg, J.: Approximation Algorithms for Disjoint Paths Problems. Ph.D. Thesis, M.I.T. (1996)"},{"key":"44_CR12","doi-asserted-by":"crossref","unstructured":"Kolliopoulos, S.G., Stein, C.: Improved approximation algorithms for unsplittable flow problems. In: Proc. 38th Annual Symposium on Foundations of Computer Science (1997)","DOI":"10.1109\/SFCS.1997.646131"},{"key":"44_CR13","doi-asserted-by":"publisher","first-page":"369","DOI":"10.1112\/jlms\/s2-17.3.369","volume":"17","author":"C.L. Lucchesi","year":"1978","unstructured":"Lucchesi, C.L., Younger, D.H.: A minimax relation for directed graphs. J. London Mathematical Society\u00a017, 369\u2013374 (1978)","journal-title":"J. London Mathematical Society"},{"key":"44_CR14","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. Combinatorial Theory Ser. B\u00a063, 65\u2013110 (1995)","journal-title":"J. Combinatorial Theory Ser. B"},{"key":"44_CR15","doi-asserted-by":"publisher","first-page":"780","DOI":"10.1137\/S0097539792224061","volume":"23","author":"A. Schrijver","year":"1994","unstructured":"Schrijver, A.: Finding k disjoint paths in a directed planar graph. SIAM J. Computing\u00a023, 780\u2013788 (1994)","journal-title":"SIAM J. Computing"},{"key":"44_CR16","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. of the ACM\u00a027, 445\u2013456 (1980)","journal-title":"J. of the ACM"},{"issue":"3","key":"44_CR17","doi-asserted-by":"publisher","first-page":"493","DOI":"10.1007\/s101070100260","volume":"91","author":"M. Skutella","year":"2002","unstructured":"Skutella, M.: Approximating the single source unsplittable min-cost flow problem. Mathematical Programming Ser. B\u00a091(3), 493\u2013514 (2002)","journal-title":"Mathematical Programming Ser. B"},{"key":"44_CR18","doi-asserted-by":"publisher","first-page":"83","DOI":"10.1016\/0166-218X(93)E0177-Z","volume":"61","author":"J. Vygen","year":"1995","unstructured":"Vygen, J.: NP-completeness of some edge-disjoint paths problems. Discrete Appl. Math.\u00a061, 83\u201390 (1995)","journal-title":"Discrete Appl. Math."},{"key":"44_CR19","unstructured":"Vygen, J.: Disjoint paths, Rep. #94846, Research Inst. for Discrete Math., U. of Bonn (1998)"}],"container-title":["Lecture Notes in Computer Science","Algorithms - ESA 2003"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-39658-1_44","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,31]],"date-time":"2019-05-31T13:00:49Z","timestamp":1559307649000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-39658-1_44"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2003]]},"ISBN":["9783540200642","9783540396581"],"references-count":19,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-39658-1_44","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2003]]}}}