{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,26]],"date-time":"2025-09-26T00:17:48Z","timestamp":1758845868838,"version":"3.40.3"},"publisher-location":"Berlin, Heidelberg","reference-count":31,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642112683"},{"type":"electronic","value":"9783642112690"}],"license":[{"start":{"date-parts":[[2009,1,1]],"date-time":"2009-01-01T00:00:00Z","timestamp":1230768000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2009,1,1]],"date-time":"2009-01-01T00:00:00Z","timestamp":1230768000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2009]]},"DOI":"10.1007\/978-3-642-11269-0_17","type":"book-chapter","created":{"date-parts":[[2009,12,1]],"date-time":"2009-12-01T08:36:15Z","timestamp":1259656575000},"page":"210-221","source":"Crossref","is-referenced-by-count":5,"title":["Paths of Bounded Length and Their Cuts: Parameterized Complexity and Algorithms"],"prefix":"10.1007","author":[{"given":"Petr A.","family":"Golovach","sequence":"first","affiliation":[]},{"given":"Dimitrios M.","family":"Thilikos","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"issue":"4","key":"17_CR1","first-page":"661","volume":"12","author":"J. Ad\u00e1mek","year":"1971","unstructured":"Ad\u00e1mek, J., Koubek, V.: Remarks on flows in network with short paths. Commentationes Mathematicae Universitatis Carolinae\u00a012(4), 661\u2013667 (1971)","journal-title":"Commentationes Mathematicae Universitatis Carolinae"},{"key":"17_CR2","doi-asserted-by":"crossref","first-page":"844","DOI":"10.1145\/210332.210337","volume":"42","author":"N. Alon","year":"1995","unstructured":"Alon, N., Yuster, R., Zwick, U.: Color-coding. J. Assoc. Comput. Mach.\u00a042, 844\u2013856 (1995)","journal-title":"J. Assoc. Comput. Mach."},{"key":"17_CR3","doi-asserted-by":"publisher","first-page":"308","DOI":"10.1016\/0196-6774(91)90006-K","volume":"12","author":"S. Arnborg","year":"1991","unstructured":"Arnborg, S., Lagergren, J., Seese, D.: Easy problems for tree-decomposable graphs. Journal of Algorithms\u00a012, 308\u2013340 (1991)","journal-title":"Journal of Algorithms"},{"key":"17_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"679","DOI":"10.1007\/11786986_59","volume-title":"Automata, Languages and Programming","author":"G. Baier","year":"2006","unstructured":"Baier, G., Erlebach, T., Hall, A., K\u00f6hler, E., Schilling, H., Skutella, M.: Length-bounded cuts and flows. In: Bugliesi, M., Preneel, B., Sassone, V., Wegener, I. (eds.) ICALP 2006. LNCS, vol.\u00a04051, pp. 679\u2013690. Springer, Heidelberg (2006)"},{"key":"17_CR5","unstructured":"Baier, G., Erlebach, T., Hall, A., K\u00f6hler, E., Kolman, P., Pangr\u00e1c, O., Schilling, H., Skutella, M.: Length-bounded cuts and flows. ACM Transactions in Algorithms (to appear)"},{"key":"17_CR6","doi-asserted-by":"publisher","first-page":"131","DOI":"10.1007\/s00037-003-0179-6","volume":"12","author":"A. Bley","year":"2003","unstructured":"Bley, A.: On the complexity of vertex-disjoint length-restricted path problems. Comput. Complexity\u00a012, 131\u2013149 (2003)","journal-title":"Comput. Complexity"},{"key":"17_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"563","DOI":"10.1007\/978-3-540-70575-8_46","volume-title":"Automata, Languages and Programming","author":"H.L. Bodlaender","year":"2008","unstructured":"Bodlaender, H.L., Downey, R.G., Fellows, M.R., Hermelin, D.: On problems without polynomial kernels (extended abstract). In: Aceto, L., Damg\u00e5rd, I., Goldberg, L.A., Halld\u00f3rsson, M.M., Ing\u00f3lfsd\u00f3ttir, A., Walukiewicz, I. (eds.) ICALP 2008, Part I. LNCS, vol.\u00a05125, pp. 563\u2013574. Springer, Heidelberg (2008)"},{"key":"17_CR8","doi-asserted-by":"publisher","first-page":"123","DOI":"10.1007\/BF01293664","volume":"14","author":"R.B. Borie","year":"1995","unstructured":"Borie, R.B.: Generation of polynomial-time algorithms for some optimization problems on tree-decomposable graphs. Algorithmica\u00a014, 123\u2013137 (1995)","journal-title":"Algorithmica"},{"key":"17_CR9","series-title":"Annals of Mathematics Studies","first-page":"215","volume-title":"On the max-flow min-cut theorem of networks, in Linear inequalities and related systems","author":"G.B. Dantzig","year":"1956","unstructured":"Dantzig, G.B., Fulkerson, D.R.: On the max-flow min-cut theorem of networks, in Linear inequalities and related systems. Annals of Mathematics Studies, vol.\u00a038, pp. 215\u2013221. Princeton University Press, Princeton (1956)"},{"key":"17_CR10","series-title":"Monographs in Computer Science","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. Monographs in Computer Science. Springer, New York (1999)"},{"key":"17_CR11","doi-asserted-by":"publisher","first-page":"317","DOI":"10.1016\/0012-365X(83)90197-8","volume":"44","author":"G. Exoo","year":"1983","unstructured":"Exoo, G.: On line disjoint paths of bounded length. Discrete Math.\u00a044, 317\u2013318 (1983)","journal-title":"Discrete Math."},{"key":"17_CR12","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1016\/j.tcs.2008.09.065","volume":"410","author":"M. Fellows","year":"2009","unstructured":"Fellows, M., Hermelin, D., Rosamond, F., Vialette, S.: On the parameterized complexity of multiple-interval graph problems. Theor. Comput. Sci.\u00a0410, 53\u201361 (2009)","journal-title":"Theor. Comput. Sci."},{"key":"17_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"36","DOI":"10.1007\/3-540-47867-1_4","volume-title":"Integer Programming and Combinatorial Optimization","author":"L.K. Fleischer","year":"2002","unstructured":"Fleischer, L.K., Skutella, M.: The quickest multicommodity flow problem. In: Cook, W.J., Schulz, A.S. (eds.) IPCO 2002. LNCS, vol.\u00a02337, pp. 36\u201353. Springer, Heidelberg (2002)"},{"key":"17_CR14","series-title":"An EATCS Series","volume-title":"Parameterized complexity theory, Texts in Theoretical Computer Science","author":"J. Flum","year":"2006","unstructured":"Flum, J., Grohe, M.: Parameterized complexity theory, Texts in Theoretical Computer Science. An EATCS Series. Springer, Berlin (2006)"},{"key":"17_CR15","doi-asserted-by":"crossref","first-page":"399","DOI":"10.4153\/CJM-1956-045-5","volume":"8","author":"L.R. Ford Jr.","year":"1956","unstructured":"Ford Jr., L.R., Fulkerson, D.R.: Maximal flow through a network. Canad. J. Math.\u00a08, 399\u2013404 (1956)","journal-title":"Canad. J. Math."},{"key":"17_CR16","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":"17_CR17","doi-asserted-by":"publisher","first-page":"473","DOI":"10.1016\/S0022-0000(03)00066-7","volume":"67","author":"V. Guruswami","year":"2003","unstructured":"Guruswami, V., Khanna, S., Rajaraman, R., Shepherd, B., Yannakakis, M.: Near-optimal hardness results and approximation algorithms for edge-disjoint paths and related problems. J. Comput. System Sci.\u00a067, 473\u2013496 (2003)","journal-title":"J. Comput. System Sci."},{"key":"17_CR18","first-page":"668","volume":"77","author":"D. Hsu","year":"1994","unstructured":"Hsu, D.: On container width and length in graphs, groups, and networks. IEICE transactions on fundamentals of electronics, communications and computer sciences\u00a077, 668\u2013680 (1994); Dedicated to Professor Paul Erd\u0151s on the occasion of his 80th birthday (Special Section on Discrete Mathematics and Its Applications)","journal-title":"IEICE transactions on fundamentals of electronics, communications and computer sciences"},{"key":"17_CR19","doi-asserted-by":"publisher","first-page":"277","DOI":"10.1002\/net.3230120306","volume":"12","author":"A. Itai","year":"1982","unstructured":"Itai, A., Perl, Y., Shiloach, Y.: The complexity of finding maximum disjoint paths with length constraints. Networks\u00a012, 277\u2013286 (1982)","journal-title":"Networks"},{"issue":"1","key":"17_CR20","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(1), 45\u201368 (1975)","journal-title":"Networks"},{"key":"17_CR21","first-page":"184","volume-title":"Proceedings of the Symposium on Discrete Algorithms","author":"P. Kolman","year":"2002","unstructured":"Kolman, P., Scheideler, C.: Improved bounds for the unsplittable flow problem. In: Proceedings of the Symposium on Discrete Algorithms, pp. 184\u2013193. ACM, New York (2002)"},{"issue":"1","key":"17_CR22","doi-asserted-by":"publisher","first-page":"20","DOI":"10.1016\/j.jalgor.2004.07.006","volume":"61","author":"P. Kolman","year":"2006","unstructured":"Kolman, P., Scheideler, C.: Improved bounds for the unsplittable flow problem. Journal of Algorithms\u00a061(1), 20\u201344 (2006)","journal-title":"Journal of Algorithms"},{"key":"17_CR23","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, T., Simchi-Levi, D.: The complexity of finding two disjoint paths with min-max objective function. Discrete Appl. Math.\u00a026, 105\u2013115 (1990)","journal-title":"Discrete Appl. Math."},{"key":"17_CR24","doi-asserted-by":"publisher","first-page":"269","DOI":"10.1007\/BF02019432","volume":"9","author":"L. Lov\u00e1sz","year":"1978","unstructured":"Lov\u00e1sz, L., Neumann Lara, V., Plummer, M.: Mengerian theorems for paths of bounded length. Period. Math. Hungar.\u00a09, 269\u2013276 (1978)","journal-title":"Period. Math. Hungar."},{"key":"17_CR25","doi-asserted-by":"publisher","first-page":"572","DOI":"10.1007\/BF01209188","volume":"96","author":"K. Menger","year":"1927","unstructured":"Menger, K.: \u00dcber regul\u00e4re Baumkurven. Math. Ann.\u00a096, 572\u2013582 (1927)","journal-title":"Math. Ann."},{"key":"17_CR26","series-title":"Oxford Lecture Series in Mathematics and its Applications","doi-asserted-by":"crossref","DOI":"10.1093\/acprof:oso\/9780198566076.001.0001","volume-title":"Invitation to fixed-parameter algorithms","author":"R. Niedermeier","year":"2006","unstructured":"Niedermeier, R.: Invitation to fixed-parameter algorithms. Oxford Lecture Series in Mathematics and its Applications, vol.\u00a031. Oxford University Press, Oxford (2006)"},{"key":"17_CR27","first-page":"275","volume":"42, 43","author":"L. Niepel","year":"1983","unstructured":"Niepel, L., \u0160afa\u0159\u00edkov\u00e1, D.: On a generalization of Menger\u2019s theorem. Acta Math. Univ. Comenian.\u00a042, 43, 275\u2013284 (1983)","journal-title":"Acta Math. Univ. Comenian."},{"key":"17_CR28","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. Journal of Combinatorial Theory. Series B\u00a063, 65\u2013110 (1995)","journal-title":"Journal of Combinatorial Theory. Series B"},{"key":"17_CR29","doi-asserted-by":"publisher","first-page":"531","DOI":"10.1002\/net.3230140405","volume":"14","author":"D. Ronen","year":"1984","unstructured":"Ronen, D., Perl, Y.: Heuristics for finding a maximum number of disjoint bounded paths. Networks\u00a014, 531\u2013544 (1984)","journal-title":"Networks"},{"key":"17_CR30","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"375","DOI":"10.1007\/3-540-62559-3_30","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"S. Tragoudas","year":"1997","unstructured":"Tragoudas, S., Varol, Y.L.: Computing disjoint paths with length constraints. In: D\u2019Amore, F., Marchetti-Spaccamela, A., Franciosa, P.G. (eds.) WG 1996. LNCS, vol.\u00a01197, pp. 375\u2013389. Springer, Heidelberg (1997)"},{"key":"17_CR31","doi-asserted-by":"publisher","first-page":"135","DOI":"10.1007\/BF01294465","volume":"15","author":"D. Wagner","year":"1995","unstructured":"Wagner, D., Weihe, K.: A linear-time algorithm for edge-disjoint paths in planar graphs. Combinatorica\u00a015, 135\u2013150 (1995)","journal-title":"Combinatorica"}],"container-title":["Lecture Notes in Computer Science","Parameterized and Exact Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-11269-0_17","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,23]],"date-time":"2023-01-23T20:35:03Z","timestamp":1674506103000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-642-11269-0_17"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009]]},"ISBN":["9783642112683","9783642112690"],"references-count":31,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-11269-0_17","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2009]]}}}