{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T00:24:04Z","timestamp":1725582244618},"publisher-location":"Berlin, Heidelberg","reference-count":20,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642208768"},{"type":"electronic","value":"9783642208775"}],"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-20877-5_51","type":"book-chapter","created":{"date-parts":[[2011,4,27]],"date-time":"2011-04-27T06:35:17Z","timestamp":1303886117000},"page":"528-539","source":"Crossref","is-referenced-by-count":3,"title":["Edge Contractions in Subclasses of Chordal Graphs"],"prefix":"10.1007","author":[{"given":"R\u00e9my","family":"Belmonte","sequence":"first","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"}]}],"member":"297","reference":[{"key":"51_CR1","doi-asserted-by":"crossref","unstructured":"Brandst\u00e4dt, A., Le, V.\u00a0B., Spinrad, J.: Graph Classes: A Survey. SIAM Monographs on Discrete Mathematics and Applications (1999)","DOI":"10.1137\/1.9780898719796"},{"key":"51_CR2","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":"51_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"72","DOI":"10.1007\/3-540-53832-1_32","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"P. Damaschke","year":"1991","unstructured":"Damaschke, P.: Induced subgraph isomorphism for cographs is NP-complete. In: M\u00f6hring, R.H. (ed.) WG 1990. LNCS, vol.\u00a0484, pp. 72\u201378. Springer, Heidelberg (1991)"},{"key":"51_CR4","volume-title":"Computers and Intractability","author":"M.R. Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability. W.H.\u00a0Freeman and Co., New York (1979)"},{"key":"51_CR5","unstructured":"George, A., Liu, J.W.: Computer Solution of Large Sparse Positive Definite. Prentice Hall Professional Technical Reference (1981)"},{"key":"51_CR6","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":"51_CR7","first-page":"87","volume":"14","author":"P. Heggernes","year":"2007","unstructured":"Heggernes, P., Kratsch, D.: Linear-time certifying recognition algorithms and forbidden induced subgraphs. Nordic Journal of Computing\u00a014, 87\u2013108 (2007)","journal-title":"Nordic Journal of Computing"},{"key":"51_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"399","DOI":"10.1007\/978-3-642-17514-5_34","volume-title":"Algorithms and Computation","author":"P. Heggernes","year":"2010","unstructured":"Heggernes, P., Meister, D., Villanger, Y.: Induced Subgraph Isomorphism on Interval and Proper Interval Graphs. In: Cheong, O., Chwa, K.-Y., Park, K. (eds.) ISAAC 2010, Part II. LNCS, vol.\u00a06507, pp. 399\u2013409. Springer, Heidelberg (2010)"},{"key":"51_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"503","DOI":"10.1007\/978-3-642-11266-9_42","volume-title":"SOFSEM 2010: Theory and Practice of Computer Science","author":"P. Hof van \u2019t","year":"2010","unstructured":"van \u2019t Hof, P., Kami\u0144ski, M., Paulusma, D., Szeider, S., Thilikos, D.M.: On Contracting Graphs to Fixed Pattern Graphs. In: van Leeuwen, J., Muscholl, A., Peleg, D., Pokorn\u00fd, J., Rumpe, B. (eds.) SOFSEM 2010. LNCS, vol.\u00a05901, pp. 503\u2013514. Springer, Heidelberg (2010)"},{"key":"51_CR10","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":"51_CR11","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":"51_CR12","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":"51_CR13","first-page":"3","volume-title":"Proceedings of the 4th Southeastern Conference on Combinatorics, Graphs Theory, and Computing","author":"L. Lov\u00e1sz","year":"1973","unstructured":"Lov\u00e1sz, L.: Coverings and colorings of hypergraphs. In: Proceedings of the 4th Southeastern Conference on Combinatorics, Graphs Theory, and Computing, pp. 3\u201312. Utilitas Mathematica Publishing, Winnipeg (1973)"},{"key":"51_CR14","series-title":"Annals of Discrete Mathematics","volume-title":"Threshold graphs and related topics","author":"N. Mahadev","year":"1995","unstructured":"Mahadev, N., Peled, U.: Threshold graphs and related topics. Annals of Discrete Mathematics, vol.\u00a056. North Holland, Amsterdam (1995)"},{"issue":"1-3","key":"51_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(1-3), 343\u2013364 (1992)","journal-title":"Discrete Mathematics"},{"key":"51_CR16","doi-asserted-by":"crossref","unstructured":"Robertson, N., Seymour, P.D.: Graph Minors.XIII. The Disjoint Paths Problem. Journal of Combinatorial Theory, Series B\u00a063(1) (1995)","DOI":"10.1006\/jctb.1995.1006"},{"key":"51_CR17","series-title":"Graduate series 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. Graduate series Mathematics and its Applications. Oxford University Press, Oxford (2003)"},{"key":"51_CR18","doi-asserted-by":"publisher","first-page":"789","DOI":"10.1090\/S0002-9939-1962-0172273-0","volume":"13","author":"E.S. Wolk","year":"1962","unstructured":"Wolk, E.S.: The comparability graph of a tree. Proceedings of the American Mathematical Society\u00a013, 789\u2013795 (1962)","journal-title":"Proceedings of the American Mathematical Society"},{"key":"51_CR19","first-page":"17","volume":"16","author":"E.S. Wolk","year":"1965","unstructured":"Wolk, E.S.: A note on \u201cThe comparability graph of a tree\u201d. Proceedings of the American Mathematical Society\u00a016, 17\u201320 (1965)","journal-title":"Proceedings of the American Mathematical Society"},{"key":"51_CR20","doi-asserted-by":"publisher","first-page":"247","DOI":"10.1016\/0166-218X(96)00094-7","volume":"69","author":"J.-H. Yan","year":"1996","unstructured":"Yan, J.-H., Chen, J.-J., Chang, G.J.: Quasi-threshold graphs. Discrete Applied Mathematics\u00a069, 247\u2013255 (1996)","journal-title":"Discrete Applied Mathematics"}],"container-title":["Lecture Notes in Computer Science","Theory and Applications of Models of Computation"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-20877-5_51","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,4,6]],"date-time":"2024-04-06T11:23:25Z","timestamp":1712402605000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-20877-5_51"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011]]},"ISBN":["9783642208768","9783642208775"],"references-count":20,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-20877-5_51","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2011]]}}}