{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:14:17Z","timestamp":1759637657386,"version":"3.40.3"},"publisher-location":"Cham","reference-count":24,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319123394"},{"type":"electronic","value":"9783319123400"}],"license":[{"start":{"date-parts":[[2014,1,1]],"date-time":"2014-01-01T00:00:00Z","timestamp":1388534400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2014,1,1]],"date-time":"2014-01-01T00:00:00Z","timestamp":1388534400000},"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":[[2014]]},"DOI":"10.1007\/978-3-319-12340-0_19","type":"book-chapter","created":{"date-parts":[[2014,10,20]],"date-time":"2014-10-20T04:27:23Z","timestamp":1413779243000},"page":"225-237","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Induced Disjoint Paths in Circular-Arc Graphs in Linear Time"],"prefix":"10.1007","author":[{"given":"Petr A.","family":"Golovach","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Dani\u00ebl","family":"Paulusma","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Erik Jan","family":"van Leeuwen","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2014,10,21]]},"reference":[{"key":"19_CR1","first-page":"501","volume":"69","author":"R Belmonte","year":"2014","unstructured":"Belmonte, R., Golovach, P.A., Heggernes, P., van \u2019t Hof, P., Kaminski, M., Paulusma, D.: Detecting fixed patterns in chordal graphs in polynomial time. Algorithmica 69, 501\u2013521 (2014)","journal-title":"Algorithmica"},{"key":"19_CR2","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1016\/0012-365X(91)90098-M","volume":"90","author":"D Bienstock","year":"1991","unstructured":"Bienstock, D.: On the complexity of testing for odd holes and induced odd paths. Discrete Math. 90, 85\u201392 (1991). See also Corrigendum, Discrete Mathematics 102 (1992), 109","journal-title":"Discrete Math."},{"key":"19_CR3","doi-asserted-by":"publisher","first-page":"335","DOI":"10.1016\/S0022-0000(76)80045-1","volume":"13","author":"KS Booth","year":"1976","unstructured":"Booth, K.S., Lueker, G.S.: Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms. J. Comput. Syst. Sci. 13, 335\u2013379 (1976)","journal-title":"J. Comput. Syst. Sci."},{"key":"19_CR4","volume-title":"Graph Theory","author":"R Diestel","year":"2005","unstructured":"Diestel, R.: Graph Theory. Springer, New York (2005). Electronic Edition"},{"key":"19_CR5","doi-asserted-by":"crossref","unstructured":"Fellows, M.R.: The Robertson-Seymour theorems: a survey of applications. In: Proceedings of the AMS-IMS-SIAM Joint Summer Research Conference, Contemporary Mathematics, vol. 89, pp. 1\u201318. American Mathematical Society, Providence (1989)","DOI":"10.1090\/conm\/089\/1006472"},{"key":"19_CR6","doi-asserted-by":"publisher","first-page":"499","DOI":"10.1007\/s00453-010-9468-z","volume":"62","author":"J Fiala","year":"2012","unstructured":"Fiala, J., Kami\u0144ski, M., Lidicky, B., Paulusma, D.: The $$k$$-in-a-path problem for claw-free graphs. Algorithmica 62, 499\u2013519 (2012)","journal-title":"Algorithmica"},{"key":"19_CR7","doi-asserted-by":"crossref","unstructured":"Fomin, F.V., Todinca, I., Villanger, Y.: Large induced subgraphs via triangulations and CMSO. In: Proceedings of SODA 2014, pp. 582\u2013593. SIAM (2014)","DOI":"10.1137\/1.9781611973402.44"},{"key":"19_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"153","DOI":"10.1007\/978-3-642-31155-0_14","volume-title":"Algorithm Theory \u2013 SWAT 2012","author":"PA Golovach","year":"2012","unstructured":"Golovach, P.A., Paulusma, D., van Leeuwen, E.J.: Induced disjoint paths in AT-Free graphs. In: Fomin, F.V., Kaski, P. (eds.) SWAT 2012. LNCS, vol. 7357, pp. 153\u2013164. Springer, Heidelberg (2012)"},{"key":"19_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"515","DOI":"10.1007\/978-3-642-33090-2_45","volume-title":"Algorithms \u2013 ESA 2012","author":"PA Golovach","year":"2012","unstructured":"Golovach, P.A., Paulusma, D., van Leeuwen, E.J.: Induced disjoint paths in claw-free graphs. In: Epstein, L., Ferragina, P. (eds.) ESA 2012. LNCS, vol. 7501, pp. 515\u2013526. Springer, Heidelberg (2012)"},{"key":"19_CR10","doi-asserted-by":"crossref","unstructured":"Golovach, P.A., Paulusma, D., van Leeuwen, E.J.: Induced disjoint paths in circular-arc graphs in linear time. CoRR abs\/1403.0789 (2014)","DOI":"10.1007\/978-3-319-12340-0_19"},{"key":"19_CR11","doi-asserted-by":"publisher","first-page":"56","DOI":"10.1016\/0196-6774(88)90023-5","volume":"9","author":"MC Golumbic","year":"1988","unstructured":"Golumbic, M.C., Hammer, P.L.: Stability in circular arc graphs. J. Algorithms 9, 56\u201363 (1988)","journal-title":"J. Algorithms"},{"key":"19_CR12","doi-asserted-by":"publisher","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":"19_CR13","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1016\/S0304-3975(97)00241-7","volume":"234","author":"M Habib","year":"2000","unstructured":"Habib, M., McConnell, R.M., Paul, C., Viennot, L.: Lex-BFS and partition refinement, with applications to transitive orientation, interval graph recognition and consecutive ones testing. Theor. Comput. Sci. 234, 59\u201384 (2000)","journal-title":"Theor. Comput. Sci."},{"key":"19_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"315","DOI":"10.1007\/978-3-319-04298-5_28","volume-title":"SOFSEM 2014: Theory and Practice of Computer Science","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., \u0160tuller, J., Tjoa, A.M. (eds.) SOFSEM 2014. LNCS, vol. 8327, pp. 315\u2013326. Springer, Heidelberg (2014)"},{"key":"19_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":"19_CR16","doi-asserted-by":"publisher","first-page":"670","DOI":"10.1016\/j.jcss.2011.10.004","volume":"78","author":"Y Kobayashi","year":"2012","unstructured":"Kobayashi, Y., Kawarabayashi, K.: A linear time algorithm for the induced disjoint paths problem in planar graphs. J. Comput. Syst. Sci. 78, 670\u2013680 (2012)","journal-title":"J. Comput. Syst. Sci."},{"key":"19_CR17","first-page":"68","volume":"18","author":"N Korte","year":"1989","unstructured":"Korte, N., M\u00f6hring, R.H.: An incremental linear-time algorithm for recognizing interval graphs SIAM. J. Comput. 18, 68\u201381 (1989)","journal-title":"J. Comput."},{"key":"19_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."},{"key":"19_CR19","doi-asserted-by":"publisher","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. SIGDA Newsl. 5, 31\u201336 (1975)","journal-title":"SIGDA Newsl."},{"key":"19_CR20","doi-asserted-by":"publisher","first-page":"93","DOI":"10.1007\/s00453-003-1032-7","volume":"37","author":"RM McConnell","year":"2003","unstructured":"McConnell, R.M.: Linear-time recognition of circular-arc graphs. Algorithmica 37, 93\u2013147 (2003)","journal-title":"Algorithmica"},{"key":"19_CR21","first-page":"256","volume":"3","author":"S Natarajan","year":"1996","unstructured":"Natarajan, S., Sprague, A.P.: Disjoint paths in circular arc graphs. Nordic J. Comput. 3, 256\u2013270 (1996)","journal-title":"Nordic J. Comput."},{"key":"19_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":"19_CR23","first-page":"295","volume-title":"Contemporary Mathematics","author":"BA Reed","year":"1993","unstructured":"Reed, B.A., Robertson, N., Schrijver, A., Seymour, P.D.: Finding disjoint trees in planar graphs in linear time. In: Robertson, N., Seymour, P.D. (eds.) Contemporary Mathematics, vol. 147, pp. 295\u2013301. American Mathematical Society, Robertson (1993)"},{"key":"19_CR24","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. Comb. Theory, Ser. B 63, 65\u2013110 (1995)","journal-title":"J. Comb. Theory, Ser. B"}],"container-title":["Lecture Notes in Computer Science","Graph-Theoretic Concepts in Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-12340-0_19","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,2,20]],"date-time":"2023-02-20T14:50:15Z","timestamp":1676904615000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-319-12340-0_19"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014]]},"ISBN":["9783319123394","9783319123400"],"references-count":24,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-12340-0_19","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2014]]},"assertion":[{"value":"21 October 2014","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}