{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T01:48:23Z","timestamp":1725587303521},"publisher-location":"Berlin, Heidelberg","reference-count":23,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642220050"},{"type":"electronic","value":"9783642220067"}],"license":[{"start":{"date-parts":[[2011,1,1]],"date-time":"2011-01-01T00:00:00Z","timestamp":1293840000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2011]]},"DOI":"10.1007\/978-3-642-22006-7_10","type":"book-chapter","created":{"date-parts":[[2011,6,20]],"date-time":"2011-06-20T03:44:05Z","timestamp":1308541445000},"page":"110-121","source":"Crossref","is-referenced-by-count":11,"title":["Tight Bounds for Linkages in Planar Graphs"],"prefix":"10.1007","author":[{"given":"Isolde","family":"Adler","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Stavros G.","family":"Kolliopoulos","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Philipp Klaus","family":"Krause","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Daniel","family":"Lokshtanov","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Saket","family":"Saurabh","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Dimitrios","family":"Thilikos","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"doi-asserted-by":"crossref","unstructured":"Adler, I., Kolliopoulos, S.G., Thilikos, D.: Planar disjoint paths completion. Submitted for publication (2011)","key":"10_CR1","DOI":"10.1007\/978-3-642-28050-4_7"},{"issue":"1-2","key":"10_CR2","first-page":"1","volume":"11","author":"H.L. Bodlaender","year":"1993","unstructured":"Bodlaender, H.L.: A tourist guide through treewidth. Acta Cybernet.\u00a011(1-2), 1\u201321 (1993)","journal-title":"Acta Cybernet."},{"key":"10_CR3","first-page":"270","volume-title":"LICS 2007","author":"A. Dawar","year":"2007","unstructured":"Dawar, A., Grohe, M., Kreutzer, S.: Locally excluding a minor. In: LICS 2007, pp. 270\u2013279. IEEE Computer Society, Los Alamitos (2007)"},{"unstructured":"Dawar, A., Kreutzer, S.: Domination problems in nowhere-dense classes. In: IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2009), pp. 157\u2013168 (2009)","key":"10_CR4"},{"key":"10_CR5","volume-title":"Graph Theory","author":"R. Diestel","year":"2005","unstructured":"Diestel, R.: Graph Theory. Springer, Heidelberg (2005)"},{"issue":"5","key":"10_CR6","doi-asserted-by":"publisher","first-page":"545","DOI":"10.1016\/j.dam.2007.02.006","volume":"156","author":"J. Ellis","year":"2008","unstructured":"Ellis, J., Warren, R.: Lower Bounds on the Pathwidth of some Grid-like Graphs. Discrete Applied Mathematics\u00a0156(5), 545\u2013555 (2008)","journal-title":"Discrete Applied Mathematics"},{"key":"10_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"514","DOI":"10.1007\/978-3-642-10631-6_53","volume-title":"Algorithms and Computation","author":"P.A. Golovach","year":"2009","unstructured":"Golovach, P.A., Kaminski, M., Paulusma, D., Thilikos, D.M.: Induced packing of odd cycles in a planar graph. In: Dong, Y., Du, D.-Z., Ibarra, O. (eds.) ISAAC 2009. LNCS, vol.\u00a05878, pp. 514\u2013523. Springer, Heidelberg (2009)"},{"key":"10_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"47","DOI":"10.1007\/978-3-540-68891-4_4","volume-title":"Integer Programming and Combinatorial Optimization","author":"K.-i. Kawarabayashi","year":"2008","unstructured":"Kawarabayashi, K.-i., Kobayashi, Y.: The induced disjoint paths problem. In: Lodi, A., Panconesi, A., Rinaldi, G. (eds.) IPCO 2008. LNCS, vol.\u00a05035, pp. 47\u201361. Springer, Heidelberg (2008)"},{"key":"10_CR9","first-page":"695","volume-title":"Proceedings of the 42nd ACM Symposium on Theory of Computing (STOC 2010)","author":"K.-i. Kawarabayashi","year":"2010","unstructured":"Kawarabayashi, K.-i., Reed, B.: Odd cycle packing. In: Proceedings of the 42nd ACM Symposium on Theory of Computing (STOC 2010), pp. 695\u2013704. ACM, New York (2010)"},{"doi-asserted-by":"crossref","unstructured":"Kawarabayashi, K.-i., Wollan, P.: A shorter proof of the graph minor algorithm: the unique linkage theorem. In: Proc. of the 42nd annual ACM Symposium on Theory of Computing (STOC 2010), pp. 687\u2013694 (2010)","key":"10_CR10","DOI":"10.1145\/1806689.1806784"},{"doi-asserted-by":"crossref","unstructured":"Kobayashi, Y., Kawarabayashi, K.-i.: Algorithms for finding an induced cycle in planar graphs and bounded genus graphs. In: Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2009), pp. 1146\u20131155. ACM-SIAM (2009)","key":"10_CR11","DOI":"10.1137\/1.9781611973068.124"},{"key":"10_CR12","first-page":"129","volume":"2","author":"M.R. Kramer","year":"1984","unstructured":"Kramer, M.R., van Leeuven, J.: The complexity of wire-routing and finding minimum area layouts for arbitrary VLSI circuits. Advances in Comp. Research\u00a02, 129\u2013146 (1984)","journal-title":"Advances in Comp. Research"},{"doi-asserted-by":"crossref","unstructured":"Lokshtanov, D., Marx, D., Saurabh, S.: Slightly superexponential parameterized problems. In: 22st ACM\u2013SIAM Symposium on Discrete Algorithms (SODA 2011), pp. 760\u2013776 (2011)","key":"10_CR13","DOI":"10.1137\/1.9781611973082.60"},{"key":"10_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"},{"issue":"1","key":"10_CR15","doi-asserted-by":"publisher","first-page":"97","DOI":"10.1007\/BF01202792","volume":"13","author":"M. Middendorf","year":"1993","unstructured":"Middendorf, M., Pfeiffer, F.: On the complexity of the disjoint paths problem. Combinatorica\u00a013(1), 97\u2013107 (1993)","journal-title":"Combinatorica"},{"key":"10_CR16","series-title":"Contemporary Mathematics","doi-asserted-by":"publisher","first-page":"295","DOI":"10.1090\/conm\/147\/01180","volume-title":"Graph Structure Theory","author":"B. Reed","year":"1991","unstructured":"Reed, B., Robertson, N., Schrijver, A., Seymour, P.D.: Finding dsjoint trees in planar graphs in linear time. In: Robertson, N., Seymour, P.D. (eds.) Graph Structure Theory. Contemporary Mathematics, vol.\u00a0147, pp. 295\u2013302. American Mathematical Society, Providence (1991)"},{"issue":"1","key":"10_CR17","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. Combin. Theory Ser. B\u00a063(1), 65\u2013110 (1995)","journal-title":"J. Combin. Theory Ser. B"},{"issue":"3","key":"10_CR18","doi-asserted-by":"publisher","first-page":"583","DOI":"10.1016\/j.jctb.2008.08.003","volume":"99","author":"N. Robertson","year":"2009","unstructured":"Robertson, N., Seymour, P.: Graph minors. XXI. Graphs with unique linkages. J. Combin. Theory Ser. B\u00a099(3), 583\u2013616 (2009)","journal-title":"J. Combin. Theory Ser. B"},{"doi-asserted-by":"crossref","unstructured":"Robertson, N., Seymour, P.D.: Graph Minors. XXII. Irrelevant vertices in linkage problems. Journal of Combinatorial Theory, Series B (to appear)","key":"10_CR19","DOI":"10.1016\/j.jctb.2007.12.007"},{"issue":"3","key":"10_CR20","doi-asserted-by":"publisher","first-page":"583","DOI":"10.1016\/j.jctb.2008.08.003","volume":"99","author":"N. Robertson","year":"2009","unstructured":"Robertson, N., Seymour, P.D.: Graph minors. XXI. Graphs with unique linkages. Journal of Combinatorial Theory, Series B\u00a099(3), 583\u2013616 (2009)","journal-title":"Journal of Combinatorial Theory, Series B"},{"issue":"4","key":"10_CR21","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. Comput.\u00a023(4), 780\u2013788 (1994)","journal-title":"SIAM J. Comput."},{"key":"10_CR22","series-title":"Polyhedra and efficiency","volume-title":"Combinatorial optimization","author":"A. Schrijver","year":"2003","unstructured":"Schrijver, A.: Combinatorial optimization. Polyhedra and efficiency, vol.\u00a0A. Springer, Berlin (2003)"},{"issue":"1","key":"10_CR23","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(1), 83\u201390 (1995)","journal-title":"Discrete Appl. Math."}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-22006-7_10","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,6,11]],"date-time":"2019-06-11T21:48:11Z","timestamp":1560289691000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-22006-7_10"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011]]},"ISBN":["9783642220050","9783642220067"],"references-count":23,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-22006-7_10","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2011]]}}}