{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,15]],"date-time":"2026-01-15T00:43:52Z","timestamp":1768437832941,"version":"3.49.0"},"publisher-location":"Berlin, Heidelberg","reference-count":17,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783642255908","type":"print"},{"value":"9783642255915","type":"electronic"}],"license":[{"start":{"date-parts":[[2011,1,1]],"date-time":"2011-01-01T00:00:00Z","timestamp":1293840000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2011]]},"DOI":"10.1007\/978-3-642-25591-5_13","type":"book-chapter","created":{"date-parts":[[2011,12,3]],"date-time":"2011-12-03T00:32:34Z","timestamp":1322872354000},"page":"110-119","source":"Crossref","is-referenced-by-count":5,"title":["Finding Contractions and Induced Minors in Chordal Graphs via Disjoint Paths"],"prefix":"10.1007","author":[{"given":"R\u00e9my","family":"Belmonte","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Petr A.","family":"Golovach","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Pinar","family":"Heggernes","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Pim","family":"van \u2019t Hof","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Marcin","family":"Kami\u0144ski","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Dani\u00ebl","family":"Paulusma","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"13_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"528","DOI":"10.1007\/978-3-642-20877-5_51","volume-title":"Theory and Applications of Models of Computation","author":"R. Belmonte","year":"2011","unstructured":"Belmonte, R., Heggernes, P., van \u2019t Hof, P.: Edge Contractions in Subclasses of Chordal Graphs. In: Ogihara, M., Tarui, J. (eds.) TAMC 2011. LNCS, vol.\u00a06648, pp. 528\u2013539. Springer, Heidelberg (2011)"},{"key":"13_CR2","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/978-1-4613-8369-7_1","volume":"56","author":"J.R.S. Blair","year":"1993","unstructured":"Blair, J.R.S., Peyton, B.: An introduction to chordal graphs and clique trees. Graph Theory and Sparse Matrix Computation\u00a056, 1\u201329 (1993)","journal-title":"Graph Theory and Sparse Matrix Computation"},{"key":"13_CR3","doi-asserted-by":"publisher","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. Journal of Graph Theory\u00a011, 71\u201379 (1987)","journal-title":"Journal of Graph Theory"},{"key":"13_CR4","doi-asserted-by":"publisher","first-page":"71","DOI":"10.1007\/BF02992776","volume":"25","author":"G.A. Dirac","year":"1961","unstructured":"Dirac, G.A.: On rigid circuit graphs. Anh. Math. Sem. Univ. Hamburg\u00a025, 71\u201376 (1961)","journal-title":"Anh. Math. Sem. Univ. Hamburg"},{"key":"13_CR5","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":"13_CR6","doi-asserted-by":"publisher","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. Journal of Combinatorial Theory, Series B\u00a016, 47\u201356 (1974)","journal-title":"Journal of Combinatorial Theory, Series B"},{"key":"13_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"339","DOI":"10.1007\/978-3-642-22993-0_32","volume-title":"Mathematical Foundations of Computer Science 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: Murlak, F., Sankowski, P. (eds.) MFCS 2011. LNCS, vol.\u00a06907, pp. 339\u2013350. Springer, Heidelberg (2011)"},{"key":"13_CR8","unstructured":"Golovach, P.A., Kami\u0144ski, M., Paulusma, D., Thilikos, D.M.: Containment relations in split graphs (manuscript)"},{"key":"13_CR9","unstructured":"van \u2019t Hof, P., Kami\u0144ski, M., Paulusma, D., Szeider, S., Thilikos, D.M.: On graph contractions and induced minors. Discrete Applied Mathematics (to appear)"},{"key":"13_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"190","DOI":"10.1007\/978-3-642-11409-0_17","volume-title":"Graph-Theoretic Concepts in Computer Science","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.\u00a05911, pp. 190\u2013201. Springer, Heidelberg (2010)"},{"key":"13_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"122","DOI":"10.1007\/978-3-642-15775-2_11","volume-title":"Algorithms \u2013 ESA 2010","author":"M. Kami\u0144ski","year":"2010","unstructured":"Kami\u0144ski, M., Paulusma, D., Thilikos, D.M.: Contractions of Planar Graphs in\u00a0Polynomial\u00a0Time. In: de Berg, M., Meyer, U. (eds.) ESA 2010. LNCS, vol.\u00a06346, pp. 122\u2013133. Springer, Heidelberg (2010)"},{"key":"13_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","DOI":"10.1007\/BFb0045375","volume-title":"Treewidth, Computations and Approximations","author":"T. Kloks","year":"1994","unstructured":"Kloks, T.: Treewidth, Computations and Approximations. LNCS, vol.\u00a0842. Springer, Heidelberg (1994)"},{"key":"13_CR13","doi-asserted-by":"publisher","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\u00a051, 178\u2013189 (2008)","journal-title":"Networks"},{"key":"13_CR14","doi-asserted-by":"publisher","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\u00a052, 32\u201356 (2008)","journal-title":"Networks"},{"key":"13_CR15","doi-asserted-by":"publisher","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 Mathematics\u00a0108, 343\u2013364 (1992)","journal-title":"Discrete Mathematics"},{"key":"13_CR16","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":"13_CR17","doi-asserted-by":"publisher","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 Journal on Computing\u00a013, 66\u2013579 (1984)","journal-title":"SIAM Journal on Computing"}],"container-title":["Lecture Notes in Computer Science","Algorithms and Computation"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-25591-5_13","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,1,26]],"date-time":"2019-01-26T16:09:39Z","timestamp":1548518979000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-25591-5_13"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011]]},"ISBN":["9783642255908","9783642255915"],"references-count":17,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-25591-5_13","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2011]]}}}