{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,18]],"date-time":"2026-01-18T10:30:17Z","timestamp":1768732217970,"version":"3.49.0"},"reference-count":26,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2014,9,28]],"date-time":"2014-09-28T00:00:00Z","timestamp":1411862400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2015,7]]},"DOI":"10.1007\/s00224-014-9580-6","type":"journal-article","created":{"date-parts":[[2014,9,26]],"date-time":"2014-09-26T23:34:50Z","timestamp":1411774490000},"page":"140-159","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":12,"title":["Finding Disjoint Paths in Split Graphs"],"prefix":"10.1007","volume":"57","author":[{"given":"Pinar","family":"Heggernes","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Pim","family":"van \u2019t Hof","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Erik Jan","family":"van Leeuwen","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Reza","family":"Saei","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2014,9,28]]},"reference":[{"issue":"8","key":"9580_CR1","doi-asserted-by":"crossref","first-page":"423","DOI":"10.1016\/j.jcss.2009.04.001","volume":"75","author":"HL Bodlaender","year":"2009","unstructured":"Bodlaender, H.L., Downey, R.G., Fellows, M.R., Hermelin, D.: On problems without polynomial kernels. J. Comp. Syst. Sci. 75(8), 423\u2013434 (2009)","journal-title":"J. Comp. Syst. Sci."},{"key":"9580_CR2","doi-asserted-by":"crossref","unstructured":"Bodlaender, H.L., Fomin, F.V., Lokshtanov, D., Penninkx, E., Saurabh, S., Thilikos, D.M.: (Meta) kernelization: In: 50th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2009, pp. 629\u2013638. IEEE Computer Society (2009)","DOI":"10.1109\/FOCS.2009.46"},{"issue":"35","key":"9580_CR3","doi-asserted-by":"crossref","first-page":"4570","DOI":"10.1016\/j.tcs.2011.04.039","volume":"412","author":"HL Bodlaender","year":"2011","unstructured":"Bodlaender, H.L., Thomasse, S., Yeo, A.: Kernel bounds for disjoint cycles and disjoint paths. Theor. Comp. Sci. 412(35), 4570\u20134578 (2011)","journal-title":"Theor. Comp. Sci."},{"key":"9580_CR4","doi-asserted-by":"crossref","unstructured":"Brandst\u00e4dt, A., Le, V.B., Spinrad, J.: Graph Classes: A Survey SIAM Monographs on Discrete Mathematics and Applications (1999)","DOI":"10.1137\/1.9780898719796"},{"key":"9580_CR5","volume-title":"Graph Theory","author":"R Diestel","year":"2005","unstructured":"Diestel, R.: Graph Theory. Springer-Verlag, Electronic Edition (2005)"},{"key":"9580_CR6","doi-asserted-by":"crossref","unstructured":"Downey, R.G., Fellows, M.R.: Parameterized Complexity. Monographs in Computer Science. Springer (1999)","DOI":"10.1007\/978-1-4612-0515-9"},{"key":"9580_CR7","doi-asserted-by":"crossref","unstructured":"Dvorak, Z., Kr\u00e1l\u2019, D., Thomas, R.: Three-coloring triangle-free planar graphs in linear time. In: Mathieu, C. (ed.), SODA 2009, pp. 1176\u20131182. ACM-SIAM (2009)","DOI":"10.1137\/1.9781611973068.127"},{"key":"9580_CR8","doi-asserted-by":"crossref","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. Comp. 5, 691\u2013703 (1976)","journal-title":"SIAM J. Comp."},{"key":"9580_CR9","first-page":"47","volume-title":"Paths, Flows, and VLSI-Layout","author":"A Frank","year":"1990","unstructured":"Frank, A.: Packing paths, circuits, and cuts \u2013 a survey. In: Korte, B., Lov\u00e1sz, L., Pr\u00f6mel, H.J., Schrijver, A (eds.) Paths, Flows, and VLSI-Layout, pp. 47\u2013100. Springer-Verlag, Berlin (1990)"},{"key":"9580_CR10","doi-asserted-by":"crossref","unstructured":"Golumbic, M.C.: Algorithmic Graph Theory and Perfect Graphs. Annals of Disc. Math. 57. Elsevier (2004)","DOI":"10.1016\/S0167-5060(04)80051-7"},{"key":"9580_CR11","doi-asserted-by":"crossref","first-page":"188","DOI":"10.1016\/j.tcs.2006.02.026","volume":"359","author":"F Gurski","year":"2006","unstructured":"Gurski, F., Wanke, E.: Vertex disjoint paths on clique-width bounded graphs. Theor. Comput. Sci. 359, 188\u2013199 (2006)","journal-title":"Theor. Comput. Sci."},{"key":"9580_CR12","doi-asserted-by":"crossref","first-page":"275","DOI":"10.1007\/BF02579333","volume":"1","author":"PL Hammer","year":"1981","unstructured":"Hammer, P.L., Simeone, B.: The splittance of a graph. Combinatorica 1, 275\u2013284 (1981)","journal-title":"Combinatorica"},{"key":"9580_CR13","first-page":"315","volume-title":"SOFSEM 2014. LNCS, vol. 8327","author":"P Heggernes","year":"2014","unstructured":"Heggernes, P., van \u2019t Hof, P., van Leeuwen, E.J., Saei, R.: Finding disjoint paths in split graphs. In: Geffert, V., Preneel, B., Rovan, B., Stuller, J., Tjoa, A.M. (eds.) SOFSEM 2014. LNCS, vol. 8327, pp. 315\u2013326 (2014)"},{"key":"9580_CR14","first-page":"190","volume-title":"WG 2009. LNCS, vol. 5911","author":"F Kammer","year":"2010","unstructured":"Kammer, F., Tholey, T.: The k-disjoint paths problem on chordal graphs. In: Paul, C., Habib, M. (eds.) WG 2009. LNCS, vol. 5911, pp. 190\u2013201 (2010)"},{"key":"9580_CR15","doi-asserted-by":"crossref","first-page":"45","DOI":"10.1002\/net.1975.5.1.45","volume":"5","author":"RM Karp","year":"1975","unstructured":"Karp, R.M.: On the complexity of combinatorial problems. Networks 5, 45\u201368 (1975)","journal-title":"Networks"},{"key":"9580_CR16","doi-asserted-by":"crossref","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.A.: The disjoint paths problem in quadratic time. J. Comb. Theory B 102, 424\u2013435 (2012)","journal-title":"J. Comb. Theory B"},{"key":"9580_CR17","doi-asserted-by":"crossref","unstructured":"Kobayashi, Y., Kawarabayashi, K.: Algorithms for finding an induced cycle in planar graphs and bounded genus graphs. In: Mathieu, C. (ed.), SODA 2009, pp. 1146\u20131155. ACM-SIAM (2009)","DOI":"10.1137\/1.9781611973068.124"},{"key":"9580_CR18","first-page":"129","volume":"2","author":"M Kramer","year":"1984","unstructured":"Kramer, M., van Leeuwen, J.: The complexity of wirerouting and finding minimum area layouts for arbitrary VLSI circuits. Adv. Comput. Res. 2, 129\u2013146 (1984)","journal-title":"Adv. Comput. Res."},{"issue":"3","key":"9580_CR19","doi-asserted-by":"crossref","first-page":"31","DOI":"10.1145\/1061425.1061430","volume":"5","author":"JF Lynch","year":"1975","unstructured":"Lynch, J.F.: The equivalence of theorem proving and the interconnection problem. ACM SIGDA Newsl. 5(3), 31\u201336 (1975)","journal-title":"ACM SIGDA Newsl."},{"key":"9580_CR20","first-page":"256","volume":"3","author":"S Natarajan","year":"1996","unstructured":"Natarajan, S., Sprague, A.P.: Disjoint paths in circular arc graphs. Nordic. J. Comp. 3, 256\u2013270 (1996)","journal-title":"Nordic. J. Comp."},{"key":"9580_CR21","doi-asserted-by":"crossref","first-page":"177","DOI":"10.1016\/S0166-218X(01)00223-2","volume":"115","author":"T Nishizeki","year":"2001","unstructured":"Nishizeki, T., Vygen, J., Zhou, X.: The edge-disjoint paths problem is NP-complete for series-parallel graphs. Discret. Appl. Math. 115, 177\u2013186 (2001)","journal-title":"Discret. Appl. Math."},{"key":"9580_CR22","first-page":"87","volume-title":"Surveys in Combinatorics","author":"BA Reed","year":"1997","unstructured":"Reed, B.A.: Tree width and tangles: A new connectivity measure and some applications. In: Bailey, R.A. (ed.) Surveys in Combinatorics, pp. 87\u2013162. Cambridge University Press, Cambridge (1997)"},{"key":"9580_CR23","doi-asserted-by":"crossref","unstructured":"Reed, B.A., Robertson, N., Schrijver, A., Seymour, P.D.: Finding disjoint trees in planar graphs in linear time. In: Contemporary Mathematics. American Mathematics Social, Providence, RI, vol. 147, pp. 295\u2013301 (1993)","DOI":"10.1090\/conm\/147\/01180"},{"issue":"1","key":"9580_CR24","doi-asserted-by":"crossref","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 B 63(1), 65\u2013110 (1995)","journal-title":"J. Comb. Theory B"},{"key":"9580_CR25","doi-asserted-by":"crossref","first-page":"85","DOI":"10.1016\/0166-218X(84)90081-7","volume":"8","author":"CA Tovey","year":"1984","unstructured":"Tovey, C.A.: A simplified NP-complete satisfiability problem. Discret. Appl. Math. 8, 85\u201389 (1984)","journal-title":"Discret. Appl. Math."},{"key":"9580_CR26","unstructured":"Vygen, J.: Disjoint paths. Technical report 94816, Research Institute for Discrete Mathematics. University of Bonn (1998)"}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-014-9580-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00224-014-9580-6\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-014-9580-6","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,15]],"date-time":"2019-08-15T09:55:27Z","timestamp":1565862927000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00224-014-9580-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,9,28]]},"references-count":26,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2015,7]]}},"alternative-id":["9580"],"URL":"https:\/\/doi.org\/10.1007\/s00224-014-9580-6","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"value":"1432-4350","type":"print"},{"value":"1433-0490","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014,9,28]]}}}