{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,13]],"date-time":"2026-02-13T08:46:53Z","timestamp":1770972413333,"version":"3.50.1"},"publisher-location":"Berlin, Heidelberg","reference-count":24,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783642311543","type":"print"},{"value":"9783642311550","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2012]]},"DOI":"10.1007\/978-3-642-31155-0_14","type":"book-chapter","created":{"date-parts":[[2012,6,13]],"date-time":"2012-06-13T02:21:27Z","timestamp":1339554087000},"page":"153-164","source":"Crossref","is-referenced-by-count":9,"title":["Induced Disjoint Paths in AT-Free Graphs"],"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","reference":[{"key":"14_CR1","unstructured":"Belmonte, R., Golovach, P.A., Heggernes, P.: van\u2019t Hof, P., Kaminski, M., Paulusma, D.: Detecting patterns in chordal graphs (preprint)"},{"key":"14_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. Disc. Math.\u00a090, 85\u201392 (1991); See also Corrigendum. Disc. Math. 102, 109 (1992)","journal-title":"Disc. Math."},{"key":"14_CR3","doi-asserted-by":"publisher","first-page":"276","DOI":"10.1137\/S0895480197326346","volume":"12","author":"H.J. Broersma","year":"1999","unstructured":"Broersma, H.J., Kloks, T., Kratsch, D., M\u00fcller, H.: Independent Sets in Asteroidal Triple-Free Graphs. SIAM J. Discrete Math.\u00a012, 276\u2013287 (1999)","journal-title":"SIAM J. Discrete Math."},{"key":"14_CR4","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":"14_CR5","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":"14_CR6","doi-asserted-by":"publisher","first-page":"299","DOI":"10.1137\/S0895480193250125","volume":"10","author":"D.G. Corneil","year":"1997","unstructured":"Corneil, D.G., Olariu, S., Stewart, L.: Asteroidal Triple-Free Graphs. SIAM J. Discrete Math.\u00a010, 299\u2013430 (1997)","journal-title":"SIAM J. Discrete Math."},{"key":"14_CR7","doi-asserted-by":"publisher","first-page":"1284","DOI":"10.1137\/S0097539795282377","volume":"28","author":"D.G. Corneil","year":"1999","unstructured":"Corneil, D.G., Olariu, S., Stewart, L.: Linear time algorithms for dominating pairs in asteroidal triple-free graphs. SIAM J. Comput.\u00a028, 1284\u20131297 (1999)","journal-title":"SIAM J. Comput."},{"key":"14_CR8","series-title":"Monographs in Computer Science","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-0515-9","volume-title":"Parameterized complexity","author":"R.G. Downey","year":"1999","unstructured":"Downey, R.G., Fellows, M.R.: Parameterized complexity. Monographs in Computer Science. Springer, New York (1999)"},{"key":"14_CR9","series-title":"Contemporary Mathematics","first-page":"1","volume-title":"Proc. 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.) Proc. AMS-IMS-SIAM Joint Summer Research Conference. Contemporary Mathematics, vol.\u00a089, pp. 1\u201318. Amer. Math. Soc., Providence (1989)"},{"key":"14_CR10","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":"14_CR11","doi-asserted-by":"crossref","unstructured":"Golovach, P.A., Paulusma, D., van Leeuwen, E.J.: Induced Disjoint Paths in Claw-Free Graphs. arXiv:1202.4419v1 [cs.DM] (2012)","DOI":"10.1007\/978-3-642-33090-2_45"},{"key":"14_CR12","doi-asserted-by":"crossref","unstructured":"Grohe, M., Kawarabayashi, K., Marx, D., Wollan, P.: Finding topological subgraphs is fixed-parameter tractable. In: Proc. STOC, pp. 479\u2013488 (2011)","DOI":"10.1145\/1993636.1993700"},{"key":"14_CR13","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":"14_CR14","doi-asserted-by":"publisher","first-page":"295","DOI":"10.1007\/s003730170043","volume":"17","author":"T. Kloks","year":"2001","unstructured":"Kloks, T., Kratsch, D., M\u00fcller, H.: On the structure of graphs with bounded asteroidal number. Graphs and Combinatorics\u00a017, 295\u2013306 (2001)","journal-title":"Graphs and Combinatorics"},{"key":"14_CR15","first-page":"670","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. JCSS\u00a078, 670\u2013680 (2012)","journal-title":"JCSS"},{"key":"14_CR16","doi-asserted-by":"publisher","first-page":"111","DOI":"10.1016\/S0166-218X(99)00128-6","volume":"99","author":"D. Kratsch","year":"2000","unstructured":"Kratsch, D.: Domination and total domination on asteroidal triple-free graphs. Discrete Applied Mathematics\u00a099, 111\u2013123 (2000)","journal-title":"Discrete Applied Mathematics"},{"key":"14_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"309","DOI":"10.1007\/978-3-540-39890-5_27","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"D. Kratsch","year":"2003","unstructured":"Kratsch, D., M\u00fcller, H., Todinca, I.: Feedback Vertex Set and Longest Induced Path on AT-Free Graphs. In: Bodlaender, H.L. (ed.) WG 2003. LNCS, vol.\u00a02880, pp. 309\u2013321. Springer, Heidelberg (2003)"},{"key":"14_CR18","doi-asserted-by":"crossref","unstructured":"Lekkerkerker, C.G., Boland, J.C.: Representation of a finite graph by a set of intervals on the real line. Fund. Math.\u00a051, 45\u201364","DOI":"10.4064\/fm-51-1-45-64"},{"key":"14_CR19","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":"14_CR20","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":"14_CR21","doi-asserted-by":"publisher","first-page":"169","DOI":"10.1006\/jctb.1994.1011","volume":"60","author":"C.J.H. McDiarmid","year":"1994","unstructured":"McDiarmid, C.J.H., Reed, B.A., Schrijver, A., Shepherd, F.B.: Induced Circuits in Planar Graphs. J.\u00a0Comb. Theory B\u00a060, 169\u2013176 (1994)","journal-title":"J.\u00a0Comb. Theory B"},{"key":"14_CR22","first-page":"256","volume":"3","author":"S. Natarajan","year":"1996","unstructured":"Natarajan, S., Sprague, A.P.: Disjoint Paths in Circular Arc Graphs. Nord. J. Comput.\u00a03, 256\u2013270 (1996)","journal-title":"Nord. J. Comput."},{"key":"14_CR23","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 B\u00a063, 65\u2013110 (1995)","journal-title":"J. Comb. Theory B"},{"key":"14_CR24","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"144","DOI":"10.1007\/978-3-642-17514-5_13","volume-title":"Algorithms and Computation","author":"J. Stacho","year":"2010","unstructured":"Stacho, J.: 3-Colouring AT-Free Graphs in Polynomial Time. In: Cheong, O., Chwa, K.-Y., Park, K. (eds.) ISAAC 2010, Part II. LNCS, vol.\u00a06507, pp. 144\u2013155. Springer, Heidelberg (2010)"}],"container-title":["Lecture Notes in Computer Science","Algorithm Theory \u2013 SWAT 2012"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-31155-0_14","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,3]],"date-time":"2019-05-03T05:52:46Z","timestamp":1556862766000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-31155-0_14"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012]]},"ISBN":["9783642311543","9783642311550"],"references-count":24,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-31155-0_14","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012]]}}}