{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:24:44Z","timestamp":1759638284169},"publisher-location":"Berlin, Heidelberg","reference-count":32,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642330896"},{"type":"electronic","value":"9783642330902"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2012]]},"DOI":"10.1007\/978-3-642-33090-2_45","type":"book-chapter","created":{"date-parts":[[2012,8,28]],"date-time":"2012-08-28T11:29:11Z","timestamp":1346153351000},"page":"515-526","source":"Crossref","is-referenced-by-count":3,"title":["Induced Disjoint Paths in Claw-Free Graphs"],"prefix":"10.1007","author":[{"given":"Petr A.","family":"Golovach","sequence":"first","affiliation":[]},{"given":"Dani\u00ebl","family":"Paulusma","sequence":"additional","affiliation":[]},{"given":"Erik Jan","family":"van Leeuwen","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"45_CR1","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 Mathematics\u00a090, 85\u201392 (1991); See also Corrigendum. Discrete Mathematics 102, 109 (1992)","journal-title":"Discrete Mathematics"},{"key":"45_CR2","doi-asserted-by":"publisher","first-page":"4570","DOI":"10.1016\/j.tcs.2011.04.039","volume":"412","author":"H.L. Bodlaender","year":"2011","unstructured":"Bodlaender, H.L., Thomass\u00e9, S., Yeo, A.: Kernel bounds for disjoint cycles and disjoint paths. Theoretical Computer Science\u00a0412, 4570\u20134578 (2011)","journal-title":"Theoretical Computer Science"},{"key":"45_CR3","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.jctb.2011.02.004","volume":"102","author":"H. Bruhn","year":"2012","unstructured":"Bruhn, H., Saito, A.: Clique or hole in claw-free graphs. Journal of Combinatorial Theory, Series B\u00a0102, 1\u201313 (2012)","journal-title":"Journal of Combinatorial Theory, Series B"},{"key":"45_CR4","series-title":"London Mathematical Society Lecture Notes Series","doi-asserted-by":"publisher","first-page":"153","DOI":"10.1017\/CBO9780511734885.008","volume-title":"Surveys in Combinatorics","author":"M. Chudnovsky","year":"2005","unstructured":"Chudnovsky, M., Seymour, P.D.: The structure of claw-free graphs. In: Webb, B.S. (ed.) Surveys in Combinatorics. London Mathematical Society Lecture Notes Series, vol.\u00a0327, pp. 153\u2013171. Cambridge University Press, Cambridge (2005)"},{"key":"45_CR5","doi-asserted-by":"publisher","first-page":"387","DOI":"10.1007\/s00493-010-2334-4","volume":"30","author":"M. Chudnovsky","year":"2010","unstructured":"Chudnovsky, M., Seymour, P.D.: The three-in-a-tree problem. Combinatorica\u00a030, 387\u2013417 (2010)","journal-title":"Combinatorica"},{"key":"45_CR6","doi-asserted-by":"publisher","first-page":"390","DOI":"10.1137\/S0097539792269095","volume":"25","author":"X. Deng","year":"1996","unstructured":"Deng, X., Hell, P., Huang, J.: Linear time representation algorithm for proper circular-arc graphs and proper interval graphs. SIAM Journal on Computing\u00a025, 390\u2013403 (1996)","journal-title":"SIAM Journal on Computing"},{"key":"45_CR7","doi-asserted-by":"publisher","first-page":"3552","DOI":"10.1016\/j.dam.2009.02.009","volume":"157","author":"N. Derhy","year":"2009","unstructured":"Derhy, N., Picouleau, C.: Finding induced trees. Discrete Applied Mathematics\u00a0157, 3552\u20133557 (2009)","journal-title":"Discrete Applied Mathematics"},{"key":"45_CR8","doi-asserted-by":"publisher","first-page":"489","DOI":"10.1007\/s00373-009-0867-3","volume":"25","author":"N. Derhy","year":"2009","unstructured":"Derhy, N., Picouleau, C., Trotignon, N.: The four-in-a-tree problem in triangle-free graphs. Graphs and Combinatorics\u00a025, 489\u2013502 (2009)","journal-title":"Graphs and Combinatorics"},{"key":"45_CR9","series-title":"Contemporary Mathematics","first-page":"1","volume-title":"Proceedings of the AMS-IMS-SIAM Joint Summer Research Conference","author":"M.R. Fellows","year":"1989","unstructured":"Fellows, M.R.: The Robertson-Seymour theorems: A survey of applications. In: Richter, R.B. (ed.) Proceedings of the AMS-IMS-SIAM Joint Summer Research Conference. Contemporary Mathematics, vol.\u00a089, pp. 1\u201318. American Mathematical Society, Providence (1989)"},{"key":"45_CR10","doi-asserted-by":"publisher","first-page":"266","DOI":"10.1007\/BF01190507","volume":"13","author":"M.R. Fellows","year":"1995","unstructured":"Fellows, M.R., Kratochv\u00edl, J., Middendorf, M., Pfeiffer, F.: The Complexity of Induced Minors and Related Problems. Algorithmica\u00a013, 266\u2013282 (1995)","journal-title":"Algorithmica"},{"key":"45_CR11","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\u00a062, 499\u2013519 (2012)","journal-title":"Algorithmica"},{"key":"45_CR12","unstructured":"Fiala, J., Kami\u0144ski, M., Paulusma, D.: A note on contracting claw-free graphs (manuscript, submitted)"},{"key":"45_CR13","unstructured":"Fiala, J., Kami\u0144ski, M., Paulusma, D.: Detecting induced star-like minors in polynomial time (manuscript, submitted)"},{"key":"45_CR14","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":"P.A. 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.\u00a07357, pp. 153\u2013164. Springer, Heidelberg (2012)"},{"key":"45_CR15","doi-asserted-by":"crossref","unstructured":"Grohe, M., Kawarabayashi, K., Marx, D., Wollan, P.: Finding topological subgraphs is fixed-parameter tractable. In: Proc. STOC 2011, pp. 479\u2013488 (2011)","DOI":"10.1145\/1993636.1993700"},{"key":"45_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"25","DOI":"10.1007\/BFb0028546","volume-title":"STACS 98","author":"M. Habib","year":"1998","unstructured":"Habib, M., Paul, C., Viennot, L.: A Synthesis on Partition Refinement: A Useful Routine for Strings, Graphs, Boolean Matrices and Automata. In: Meinel, C., Morvan, M. (eds.) STACS 1998. LNCS, vol.\u00a01373, pp. 25\u201338. Springer, Heidelberg (1998)"},{"key":"45_CR17","doi-asserted-by":"crossref","DOI":"10.21236\/AD0705364","volume-title":"Graph Theory","author":"F. Harary","year":"1969","unstructured":"Harary, F.: Graph Theory. Addison-Wesley, Reading MA (1969)"},{"key":"45_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"462","DOI":"10.1007\/978-3-642-22006-7_39","volume-title":"Automata, Languages and Programming","author":"D. Hermelin","year":"2011","unstructured":"Hermelin, D., Mnich, M., van Leeuwen, E.J., Woeginger, G.J.: Domination When the Stars Are Out. In: Aceto, L., Henzinger, M., Sgall, J. (eds.) ICALP 2011, Part I. LNCS, vol.\u00a06755, pp. 462\u2013473. Springer, Heidelberg (2011)"},{"key":"45_CR19","doi-asserted-by":"crossref","unstructured":"Hermelin, D., Mnich, M., van Leeuwen, E.J., Woeginger, G.J.: Domination when the stars are out. arXiv:1012.0012v1 [cs.DS]","DOI":"10.1145\/3301445"},{"key":"45_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 complexity of combinatorial problems. Networks\u00a05, 45\u201368 (1975)","journal-title":"Networks"},{"key":"45_CR21","doi-asserted-by":"publisher","first-page":"215","DOI":"10.1002\/jgt.20334","volume":"228","author":"A. King","year":"2008","unstructured":"King, A., Reed, B.: Bounding \u03c7 in terms of \u03c9 and \u03b4 for quasi-line graphs. Journal of Graph Theory\u00a0228, 215\u2013228 (2008)","journal-title":"Journal of Graph Theory"},{"key":"45_CR22","first-page":"1146","volume-title":"Proc. SODA 2009","author":"Y. Kobayashi","year":"2009","unstructured":"Kobayashi, Y., Kawarabayashi, K.: Algorithms for finding an induced cycle in planar graphs and bounded genus graphs. In: Mathieu, C. (ed.) Proc. SODA 2009, pp. 1146\u20131155. ACM Press, New York (2009)"},{"key":"45_CR23","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. Journal of Computer and System Sciences\u00a078, 670\u2013680 (2012)","journal-title":"Journal of Computer and System Sciences"},{"key":"45_CR24","doi-asserted-by":"publisher","first-page":"3540","DOI":"10.1016\/j.dam.2009.02.015","volume":"157","author":"B. L\u00e9v\u00eaque","year":"2009","unstructured":"L\u00e9v\u00eaque, B., Lin, D.Y., Maffray, F., Trotignon, N.: Detecting induced subgraphs. Discrete Applied Mathematics\u00a0157, 3540\u20133551 (2009)","journal-title":"Discrete Applied Mathematics"},{"key":"45_CR25","doi-asserted-by":"publisher","first-page":"1644","DOI":"10.1016\/j.dam.2010.06.005","volume":"158","author":"W. Liu","year":"2010","unstructured":"Liu, W., Trotignon, N.: The k-in-a-tree problem for graphs of girth at least k. Discrete Applied Mathematics\u00a0158, 1644\u20131649 (2010)","journal-title":"Discrete Applied Mathematics"},{"key":"45_CR26","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. SIGDA Newsletter\u00a05, 31\u201336 (1975)","journal-title":"SIGDA Newsletter"},{"key":"45_CR27","doi-asserted-by":"publisher","first-page":"93","DOI":"10.1007\/s00453-003-1032-7","volume":"37","author":"R.M. McConnell","year":"2003","unstructured":"McConnell, R.M.: Linear-Time Recognition of Circular-Arc Graphs. Algorithmica\u00a037, 93\u2013147 (2003)","journal-title":"Algorithmica"},{"key":"45_CR28","first-page":"256","volume":"3","author":"S. Natarajan","year":"1996","unstructured":"Natarajan, S., Sprague, A.P.: Disjoint paths in circular arc graphs. Nordic Journal of Computing\u00a03, 256\u2013270 (1996)","journal-title":"Nordic Journal of Computing"},{"key":"45_CR29","doi-asserted-by":"crossref","unstructured":"Niedermeier, R.: Invitation to Fixed-Parameter Algorithms. Oxford Lecture Series in Mathematics and its Applications. Oxford University Press (2006)","DOI":"10.1093\/acprof:oso\/9780198566076.001.0001"},{"key":"45_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.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":"45_CR31","doi-asserted-by":"publisher","first-page":"108","DOI":"10.1016\/0020-0190(73)90029-X","volume":"2","author":"N.D. Roussopoulos","year":"1973","unstructured":"Roussopoulos, N.D.: A max {m,n} algorithm for determining the graph H from its line graph G. Information Processing Letters\u00a02, 108\u2013112 (1973)","journal-title":"Information Processing Letters"},{"key":"45_CR32","doi-asserted-by":"publisher","first-page":"217","DOI":"10.1006\/jctb.1996.1732","volume":"70","author":"Z. Ryj\u00e1\u010dek","year":"1997","unstructured":"Ryj\u00e1\u010dek, Z.: On a closure concept in claw-free graphs. Journal of Combinatorial Theory, Series B\u00a070, 217\u2013224 (1997)","journal-title":"Journal of Combinatorial Theory, Series B"}],"container-title":["Lecture Notes in Computer Science","Algorithms \u2013 ESA 2012"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-33090-2_45","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,7]],"date-time":"2019-05-07T02:11:50Z","timestamp":1557195110000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-33090-2_45"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012]]},"ISBN":["9783642330896","9783642330902"],"references-count":32,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-33090-2_45","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2012]]}}}