{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,25]],"date-time":"2025-11-25T08:50:53Z","timestamp":1764060653428,"version":"3.40.3"},"publisher-location":"Berlin, Heidelberg","reference-count":33,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783662476659"},{"type":"electronic","value":"9783662476666"}],"license":[{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2015]]},"DOI":"10.1007\/978-3-662-47666-6_1","type":"book-chapter","created":{"date-parts":[[2015,6,19]],"date-time":"2015-06-19T07:46:47Z","timestamp":1434700007000},"page":"3-10","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Towards the Graph Minor Theorems for Directed Graphs"],"prefix":"10.1007","author":[{"given":"Ken-Ichi","family":"Kawarabayashi","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Stephan","family":"Kreutzer","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2015,6,20]]},"reference":[{"key":"1_CR1","doi-asserted-by":"publisher","first-page":"11","DOI":"10.1016\/0166-218X(89)90031-0","volume":"23","author":"S Arnborg","year":"1989","unstructured":"Arnborg, S., Proskurowski, A.: Linear time algorithms for NP-hard problems restricted to partial $$k$$-trees. Discrete Appl. Math. 23, 11\u201324 (1989)","journal-title":"Discrete Appl. Math."},{"key":"1_CR2","doi-asserted-by":"publisher","first-page":"1305","DOI":"10.1137\/S0097539793251219","volume":"25","author":"HL Bodlaender","year":"1996","unstructured":"Bodlaender, H.L.: A linear-time algorithm for finding tree-decomposition of small treewidth. SIAM J. Comput. 25, 1305\u20131317 (1996)","journal-title":"SIAM J. Comput."},{"key":"1_CR3","doi-asserted-by":"crossref","unstructured":"Chekuri, C., Chuzhoy, J.: Polynomial bounds for the grid-minor theorem. In: Symp. on Theory of Computing (STOC), pp. 60\u201369 (2014)","DOI":"10.1145\/2591796.2591813"},{"key":"1_CR4","doi-asserted-by":"crossref","unstructured":"Courcelle, B.: Graph rewriting: An algebraic and logic approach, in Handbook of Theoretical Computer Science 2, pp. 194\u2013242. Elsevier (1990)","DOI":"10.1016\/B978-0-444-88074-1.50010-X"},{"key":"1_CR5","doi-asserted-by":"crossref","unstructured":"Cygan, M., Marx, D., Pilipczuk, M., Pilipczuk, M.: The planar directed k-vertex-disjoint paths problem is fixed-parameter tractable. In: 54th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pp. 197\u2013206 (2013)","DOI":"10.1109\/FOCS.2013.29"},{"key":"1_CR6","doi-asserted-by":"publisher","first-page":"501","DOI":"10.1137\/S0895480103433410","volume":"18","author":"ED Demaine","year":"2004","unstructured":"Demaine, E.D., Fomin, F.V., Hajiaghayi, M., Thilikos, D.M.: Bidimensional parameters and local treewidth. SIAM J. Discrete Mathematics 18, 501\u2013511 (2004)","journal-title":"SIAM J. Discrete Mathematics"},{"key":"1_CR7","doi-asserted-by":"publisher","first-page":"866","DOI":"10.1145\/1101821.1101823","volume":"52","author":"ED Demaine","year":"2005","unstructured":"Demaine, E.D., Fomin, F.V., Hajiaghayi, M., Thilikos, D.M.: Subexponential parameterized algorithms on graphs of bounded genus and $$H$$-minor-free graphs. J. ACM 52, 866\u2013893 (2005)","journal-title":"J. ACM"},{"key":"1_CR8","unstructured":"Demaine, E.D., Hajiaghayi, M.: Bidimensionality: new connections between FPT algorithms and PTASs. In: Proc. 16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 590\u2013601 (2005)"},{"key":"1_CR9","doi-asserted-by":"publisher","first-page":"19","DOI":"10.1007\/s00493-008-2140-4","volume":"28","author":"ED Demaine","year":"2008","unstructured":"Demaine, E.D., Hajiaghayi, M.: Linearity of grid minors in treewidth with applications through bidimensionality. Combinatorica 28, 19\u201336 (2008)","journal-title":"Combinatorica"},{"key":"1_CR10","doi-asserted-by":"publisher","first-page":"61","DOI":"10.1006\/jctb.1998.1862","volume":"75","author":"R Diestel","year":"1999","unstructured":"Diestel, R., Gorbunov, K.Y., Jensen, T.R., Thomassen, C.: Highly connected sets and the excluded grid theorem. J. Combin. Theory Ser. B 75, 61\u201373 (1999)","journal-title":"J. Combin. Theory Ser. B"},{"key":"1_CR11","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.E., Wyllie, J.: The directed subgraph homeomorphism problem. Theor. Comput. Sci. 10, 111\u2013121 (1980)","journal-title":"Theor. Comput. Sci."},{"key":"1_CR12","doi-asserted-by":"crossref","unstructured":"Grohe, M., Kawarabayashi, K., Marx, D., Wollan, P.: Finding topological subgraphs is fixed-parameter tractable. In: The 43rd ACM Symposium on Theory of Computing (STOC 2011), pp. 479\u2013488","DOI":"10.1145\/1993636.1993700"},{"issue":"1","key":"1_CR13","doi-asserted-by":"publisher","first-page":"138","DOI":"10.1006\/jctb.2000.2031","volume":"82","author":"T Johnson","year":"2001","unstructured":"Johnson, T., Robertson, N., Seymour, P.D., Thomas, R.: Directed tree-width. J. Comb. Theory, Ser. B 82(1), 138\u2013154 (2001)","journal-title":"J. Comb. Theory, Ser. B"},{"key":"1_CR14","unstructured":"Johnson, T., Robertson, N., Seymour, P.D., Thomas, R.: Excluding a grid minor in digraphs (2001). (unpublished manuscript)"},{"key":"1_CR15","doi-asserted-by":"crossref","unstructured":"Kawarabayashi, K., Wollan, P.: A shorter proof of the graph minors algorithm - the unique linkage theorem. In: Proc. 42nd ACM Symposium on Theory of Computing (STOC 2010), pp. 687\u2013694 (2010). A full version of this paper http:\/\/research.nii.ac.jp\/~k_keniti\/uniquelink.pdf","DOI":"10.1145\/1806689.1806784"},{"key":"1_CR16","unstructured":"Kawarabayashi, K., Kobayashi, Y.: Linear min-max relation between the treewidth of h-minor-free graphs and its largest grid. In: D\u00fcrr, C., Wilke, T. (eds.) STACS, volume 14 of LIPIcs, pp. 278\u2013289. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik (2012)"},{"key":"1_CR17","doi-asserted-by":"publisher","first-page":"424","DOI":"10.1016\/j.jctb.2011.07.004","volume":"102","author":"K Kawarabayashi","year":"2012","unstructured":"Kawarabayashi, K., Kobayashi, Y., Reed, B.: The disjoint paths problem in quadratic time. J. Combin. Theory Ser. B. 102, 424\u2013435 (2012)","journal-title":"J. Combin. Theory Ser. B."},{"key":"1_CR18","doi-asserted-by":"crossref","unstructured":"Kawarabayashi, K., Kreutzer, S.: An excluded grid theorem for digraphs with forbidden minors. In: ACM\/SIAM Symposium on Discrete Algorithms (SODA) (2014)","DOI":"10.1137\/1.9781611973402.6"},{"key":"1_CR19","doi-asserted-by":"crossref","unstructured":"Kawarabayashi, K., Kobayashi, Y., Kreutzer, S.: An excluded half-integral grid theorem for digraphs and the directed disjoint paths problem. In: Proc. of the ACM Symposium on Theory of Computing (STOC), pp. 70\u201378 (2014)","DOI":"10.1145\/2591796.2591876"},{"key":"1_CR20","doi-asserted-by":"crossref","unstructured":"Kawarabayashi, K., Kreutzer, S.: The directed excluded grid theorem. In: STOC 2015. arXiv:1411.5681 [cs.DM]","DOI":"10.1145\/2746539.2746586"},{"key":"1_CR21","doi-asserted-by":"crossref","unstructured":"Kawarabayashi, K., Reed, B.: A nearly linear time algorithm for the half-integral disjoint paths packing. In: ACM-SIAM Symposium on Discrete Algorithms (SODA 2008), pp. 446\u2013454","DOI":"10.1137\/1.9781611973068.128"},{"key":"1_CR22","doi-asserted-by":"crossref","unstructured":"Kleinberg, J.: Decision algorithms for unsplittable flows and the half-disjoint paths problem. In: Proc. 30th ACM Symposium on Theory of Computing (STOC), pp. 530\u2013539 (1998)","DOI":"10.1145\/276698.276867"},{"key":"1_CR23","unstructured":"Leaf, A., Seymour, P.: Treewidth and planar minors (2012)"},{"key":"1_CR24","doi-asserted-by":"crossref","unstructured":"Reed, B.: Finding approximate separators and computing tree width quickly. In: The 24th ACM Symposium on Theory of Computing (STOC 1992)","DOI":"10.1145\/129712.129734"},{"key":"1_CR25","doi-asserted-by":"crossref","unstructured":"Reed, B.: Tree width and tangles: a new connectivity measure and some applications, in Surveys in Combinatorics, London Math. Soc. Lecture Note Ser. 241, pp. 87\u2013162. Cambridge Univ. Press, Cambridge (1997)","DOI":"10.1017\/CBO9780511662119.006"},{"key":"1_CR26","doi-asserted-by":"publisher","first-page":"222","DOI":"10.1016\/S1571-0653(05)80061-7","volume":"3","author":"B Reed","year":"1999","unstructured":"Reed, B.: Introducing directed tree-width. Electronic Notes in Discrete Mathematics 3, 222\u2013229 (1999)","journal-title":"Electronic Notes in Discrete Mathematics"},{"issue":"4","key":"1_CR27","doi-asserted-by":"publisher","first-page":"535","DOI":"10.1007\/BF01271272","volume":"16","author":"BA Reed","year":"1996","unstructured":"Reed, B.A., Robertson, N., Seymour, P.D., Thomas, R.: Packing directed circuits. Combinatorica 16(4), 535\u2013554 (1996)","journal-title":"Combinatorica"},{"key":"1_CR28","unstructured":"Robertson, N., Seymour, P.D.: Graph minors I - XXIII, 1982\u20132010. Appearing in Journal of Combinatorial Theory, Series B from 1982 till 2010"},{"key":"1_CR29","doi-asserted-by":"publisher","first-page":"92","DOI":"10.1016\/0095-8956(86)90030-4","volume":"41","author":"N Robertson","year":"1986","unstructured":"Robertson, N., Seymour, P.D.: Graph minors. V. Excluding a planar graph. J. Combin. Theory Ser. B 41, 92\u2013114 (1986)","journal-title":"J. Combin. Theory Ser. B"},{"key":"1_CR30","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.: Graph minors XIII. The disjoint paths problem. Journal of Combinatorial Theory, Series B 63, 65\u2013110 (1995)","journal-title":"Journal of Combinatorial Theory, Series B"},{"key":"1_CR31","doi-asserted-by":"publisher","first-page":"323","DOI":"10.1006\/jctb.1994.1073","volume":"62","author":"N Robertson","year":"1994","unstructured":"Robertson, N., Seymour, P.D., Thomas, R.: Quickly excluding a planar graph. J. Combin. Theory Ser. B 62, 323\u2013348 (1994)","journal-title":"J. Combin. Theory Ser. B"},{"issue":"4","key":"1_CR32","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 Jornal on Computing 23(4), 780\u2013788 (1994)","journal-title":"SIAM Jornal on Computing"},{"key":"1_CR33","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"482","DOI":"10.1007\/978-3-540-39658-1_44","volume-title":"Algorithms - ESA 2003","author":"A Slivkins","year":"2003","unstructured":"Slivkins, A.: Parameterized tractability of edge-disjoint paths on directed acyclic graphs. In: Di Battista, G., Zwick, U. (eds.) ESA 2003. LNCS, vol. 2832, pp. 482\u2013493. Springer, Heidelberg (2003)"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages, and Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-662-47666-6_1","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,31]],"date-time":"2023-01-31T04:13:27Z","timestamp":1675138407000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-662-47666-6_1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015]]},"ISBN":["9783662476659","9783662476666"],"references-count":33,"URL":"https:\/\/doi.org\/10.1007\/978-3-662-47666-6_1","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2015]]},"assertion":[{"value":"20 June 2015","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}