{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,1]],"date-time":"2026-01-01T10:03:59Z","timestamp":1767261839277},"reference-count":35,"publisher":"Springer Science and Business Media LLC","license":[{"start":{"date-parts":[[2013,1,25]],"date-time":"2013-01-25T00:00:00Z","timestamp":1359072000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"DOI":"10.1007\/s00453-013-9748-5","type":"journal-article","created":{"date-parts":[[2013,1,24]],"date-time":"2013-01-24T18:04:42Z","timestamp":1359050682000},"source":"Crossref","is-referenced-by-count":8,"title":["Detecting Fixed Patterns in Chordal Graphs in Polynomial Time"],"prefix":"10.1007","author":[{"given":"R\u00e9my","family":"Belmonte","sequence":"first","affiliation":[]},{"given":"Petr A.","family":"Golovach","sequence":"additional","affiliation":[]},{"given":"Pinar","family":"Heggernes","sequence":"additional","affiliation":[]},{"given":"Pim","family":"van\u00a0\u2019t Hof","sequence":"additional","affiliation":[]},{"given":"Marcin","family":"Kami\u0144ski","sequence":"additional","affiliation":[]},{"given":"Dani\u00ebl","family":"Paulusma","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2013,1,25]]},"reference":[{"key":"9748_CR1","series-title":"LNCS","first-page":"110","volume-title":"Proceedings of ISAAC 2011","author":"R. Belmonte","year":"2011","unstructured":"Belmonte, R., Golovach, P.A., Heggernes, P., van \u2019t Hof, P., Kami\u0144ski, M., Paulusma, D.: Finding contractions and induced minors in chordal graphs via disjoint paths. In: Proceedings of ISAAC 2011. LNCS, vol.\u00a07074, pp.\u00a0110\u2013119. Springer, Berlin (2011)"},{"key":"9748_CR2","series-title":"LNCS","first-page":"528","volume-title":"Proceedings of TAMC 2011","author":"R. Belmonte","year":"2011","unstructured":"Belmonte, R., Heggernes, P., van \u2019t Hof, P.: Edge contractions in subclasses of chordal graphs. In: Proceedings of TAMC 2011. LNCS, vol.\u00a06648, pp.\u00a0528\u2013539. Springer, Berlin (2011)"},{"key":"9748_CR3","doi-asserted-by":"crossref","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 Math. 102, 109 (1992)","journal-title":"Discrete Math."},{"key":"9748_CR4","series-title":"IMA Volumes in Mathematics and Its Applications","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/978-1-4613-8369-7_1","volume-title":"Graph Theory and Sparse Matrix Computations","author":"J.R.S. Blair","year":"1993","unstructured":"Blair, J.R.S., Peyton, B.W.: An introduction to chordal graphs and clique trees. In: Graph Theory and Sparse Matrix Computations. IMA Volumes in Mathematics and Its Applications, vol.\u00a056, pp.\u00a01\u201329. Springer, Berlin (1993)"},{"key":"9748_CR5","doi-asserted-by":"crossref","first-page":"335","DOI":"10.1016\/S0022-0000(76)80045-1","volume":"13","author":"K.S. 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":"9748_CR6","doi-asserted-by":"crossref","DOI":"10.1137\/1.9780898719796","volume-title":"Graph Classes: A Survey","author":"A. Brandst\u00e4dt","year":"1999","unstructured":"Brandst\u00e4dt, A., Le, V.B., Spinrad, J.P.: Graph Classes: A Survey. SIAM, Philadelphia (1999)"},{"key":"9748_CR7","doi-asserted-by":"crossref","first-page":"71","DOI":"10.1002\/jgt.3190110111","volume":"11","author":"A.E. Brouwer","year":"1987","unstructured":"Brouwer, A.E., Veldman, H.J.: Contractibility and NP-completeness. J. Graph Theory 11, 71\u201379 (1987)","journal-title":"J. Graph Theory"},{"key":"9748_CR8","doi-asserted-by":"crossref","first-page":"12","DOI":"10.1016\/0890-5401(90)90043-H","volume":"85","author":"B. Courcelle","year":"1990","unstructured":"Courcelle, B.: The monadic second-order logic of graphs. I. Recognizable sets of finite graphs. Inf. Comput. 85, 12\u201375 (1990)","journal-title":"Inf. Comput."},{"key":"9748_CR9","doi-asserted-by":"crossref","first-page":"71","DOI":"10.1007\/BF02992776","volume":"25","author":"G.A. Dirac","year":"1961","unstructured":"Dirac, G.A.: On rigid circuit graphs. Abh. Math. Semin. Univ. Hamb. 25, 71\u201376 (1961)","journal-title":"Abh. Math. Semin. Univ. Hamb."},{"key":"9748_CR10","doi-asserted-by":"crossref","first-page":"109","DOI":"10.1016\/0304-3975(94)00097-3","volume":"141","author":"R.G. Downey","year":"1995","unstructured":"Downey, R.G., Fellows, M.R.: Fixed-parameter\u00a0tractability and completeness II: On completeness for W[1]. Theor. Comput. Sci. 141, 109\u2013131 (1995)","journal-title":"Theor. Comput. Sci."},{"key":"9748_CR11","doi-asserted-by":"crossref","first-page":"499","DOI":"10.1007\/s00453-010-9468-z","volume":"62","author":"J. Fiala","year":"2012","unstructured":"Fiala, J., Kami\u0144ski, M., Lidick\u00fd, B., Paulusma, D.: The k-in-a-path problem for claw-free graphs. Algorithmica 62, 499\u2013519 (2012)","journal-title":"Algorithmica"},{"key":"9748_CR12","unstructured":"Fiala, J., Kami\u0144ski, M., Paulusma, D.: A note on contracting claw-free graphs. Manuscript (2011)"},{"key":"9748_CR13","doi-asserted-by":"crossref","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 13, 266\u2013282 (1995)","journal-title":"Algorithmica"},{"key":"9748_CR14","volume-title":"Parameterized Complexity Theory","author":"J. Flum","year":"2006","unstructured":"Flum, J., Grohe, M.: Parameterized Complexity Theory. Springer, Berlin (2006)"},{"key":"9748_CR15","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"M.R. Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman, New York (1979)"},{"key":"9748_CR16","doi-asserted-by":"crossref","first-page":"47","DOI":"10.1016\/0095-8956(74)90094-X","volume":"16","author":"F. Gavril","year":"1974","unstructured":"Gavril, F.: The intersection graphs of subtrees in trees are exactly the chordal graphs. J. Comb. Theory, Ser. B 16, 47\u201356 (1974)","journal-title":"J. Comb. Theory, Ser. B"},{"key":"9748_CR17","volume-title":"Computer Solutions of Large Sparse Positive Definite Systems","author":"A. George","year":"1981","unstructured":"George, A., Liu, J.W.: Computer Solutions of Large Sparse Positive Definite Systems. Prentice Hall, New York (1981)"},{"key":"9748_CR18","series-title":"LNCS","first-page":"339","volume-title":"Proceedings of MFCS 2011","author":"P.A. Golovach","year":"2011","unstructured":"Golovach, P.A., Kami\u0144ski, M., Paulusma, D.: Contracting a chordal graph to a split graph or a tree. In: Proceedings of MFCS 2011. LNCS, vol.\u00a06907, pp.\u00a0339\u2013350. Springer, Berlin (2011)"},{"key":"9748_CR19","doi-asserted-by":"crossref","first-page":"155","DOI":"10.1016\/j.dam.2011.10.004","volume":"160","author":"P.A. Golovach","year":"2012","unstructured":"Golovach, P.A., Kami\u0144ski, M., Paulusma, D., Thilikos, D.M.: Containment relations in split graphs. Discrete Appl. Math. 160, 155\u2013163 (2012)","journal-title":"Discrete Appl. Math."},{"key":"9748_CR20","series-title":"Annals of Discrete Mathematics","volume-title":"Algorithmic Graph Theory and Perfect Graphs","author":"M.C. Golumbic","year":"2004","unstructured":"Golumbic, M.C.: Algorithmic Graph Theory and Perfect Graphs. Annals of Discrete Mathematics, vol.\u00a057. Elsevier, Amsterdam (2004)"},{"key":"9748_CR21","first-page":"479","volume-title":"Proceedings of STOC 2011","author":"M. Grohe","year":"2011","unstructured":"Grohe, M., Kawarabayashi, K., Marx, D., Wollan, P.: Finding topological subgraphs is fixed-parameter\u00a0tractable. In: Proceedings of STOC 2011, pp. 479\u2013488 (2011)"},{"key":"9748_CR22","doi-asserted-by":"crossref","first-page":"799","DOI":"10.1016\/j.dam.2010.05.005","volume":"160","author":"P. Hof van \u2019t","year":"2012","unstructured":"van \u2019t Hof, P., Kami\u0144ski, M., Paulusma, D., Szeider, S., Thilikos, D.M.: On graph contractions and induced minors. Discrete Appl. Math. 160, 799\u2013809 (2012)","journal-title":"Discrete Appl. Math."},{"key":"9748_CR23","doi-asserted-by":"crossref","first-page":"4834","DOI":"10.1016\/j.tcs.2009.06.028","volume":"410","author":"P. Hof van \u2019t","year":"2009","unstructured":"van \u2019t Hof, P., Paulusma, D., Woeginger, G.J.: Partitioning graphs in connected parts. Theor. Comput. Sci. 410, 4834\u20134843 (2009)","journal-title":"Theor. Comput. Sci."},{"key":"9748_CR24","volume-title":"Proceedings of STACS","author":"M. Kami\u0144ski","year":"2012","unstructured":"Kami\u0144ski, M., Thilikos, D.M.: Contraction checking in graphs on surfaces. In: Proceedings of STACS, 2012, to appear"},{"key":"9748_CR25","series-title":"LNCS","volume-title":"Treewidth, Computations and Approximations","author":"T. Kloks","year":"1994","unstructured":"Kloks, T.: Treewidth, Computations and Approximations. LNCS, vol. 842. Springer, Berlin (1994)"},{"key":"9748_CR26","doi-asserted-by":"crossref","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 Appl. Math. 157, 3540\u20133551 (2009)","journal-title":"Discrete Appl. Math."},{"key":"9748_CR27","doi-asserted-by":"crossref","first-page":"178","DOI":"10.1002\/net.20214","volume":"51","author":"A. Levin","year":"2008","unstructured":"Levin, A., Paulusma, D., Woeginger, G.J.: The computational complexity of graph contractions I: polynomially solvable and NP-complete cases. Networks 51, 178\u2013189 (2008)","journal-title":"Networks"},{"key":"9748_CR28","doi-asserted-by":"crossref","first-page":"32","DOI":"10.1002\/net.20249","volume":"52","author":"A. Levin","year":"2008","unstructured":"Levin, A., Paulusma, D., Woeginger, G.J.: The computational complexity of graph contractions II: two tough polynomially solvable cases. Networks 52, 32\u201356 (2008)","journal-title":"Networks"},{"key":"9748_CR29","doi-asserted-by":"crossref","first-page":"343","DOI":"10.1016\/0012-365X(92)90687-B","volume":"108","author":"J. Matou\u0161ek","year":"1992","unstructured":"Matou\u0161ek, J., Thomas, R.: On the complexity of finding iso- and other morphisms for partial k-trees. Discrete Math. 108, 343\u2013364 (1992)","journal-title":"Discrete Math."},{"key":"9748_CR30","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. 3, 256\u2013270 (1996)","journal-title":"Nord. J. Comput."},{"key":"9748_CR31","doi-asserted-by":"crossref","DOI":"10.1093\/acprof:oso\/9780198566076.001.0001","volume-title":"Invitation to Fixed-Parameter Algorithms","author":"R. Niedermeier","year":"2006","unstructured":"Niedermeier, R.: Invitation to Fixed-Parameter Algorithms. Oxford University Press, Oxford (2006)"},{"key":"9748_CR32","unstructured":"de Ridder, H.N., et\u00a0al.: Information System on Graph Classes and their Inclusions (ISGCI). http:\/\/www.graphclasses.org , 2001\u20132012"},{"key":"9748_CR33","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, Ser. B 63, 65\u2013110 (1995)","journal-title":"J. Comb. Theory, Ser. B"},{"key":"9748_CR34","series-title":"Oxford Lecture Series in Mathematics and Its Applications","doi-asserted-by":"crossref","DOI":"10.1093\/oso\/9780198509424.001.0001","volume-title":"Phylogenetics","author":"C. Semple","year":"2003","unstructured":"Semple, C., Steel, M.: Phylogenetics. Oxford Lecture Series in Mathematics and Its Applications. Oxford University Press, Oxford (2003)"},{"key":"9748_CR35","doi-asserted-by":"crossref","first-page":"66","DOI":"10.1137\/0213035","volume":"13","author":"R.E. Tarjan","year":"1984","unstructured":"Tarjan, R.E., Yannakakis, M.: Simple linear-time algorithms to test chordality of graphs, test acyclicity of hypergraphs, and selectively reduce acyclic hypergraphs. SIAM J. Comput. 13, 66\u2013579 (1984)","journal-title":"SIAM J. Comput."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-013-9748-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-013-9748-5\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-013-9748-5","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,5,5]],"date-time":"2024-05-05T05:11:56Z","timestamp":1714885916000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-013-9748-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,1,25]]},"references-count":35,"alternative-id":["9748"],"URL":"https:\/\/doi.org\/10.1007\/s00453-013-9748-5","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013,1,25]]}}}