{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,8]],"date-time":"2024-09-08T10:29:50Z","timestamp":1725791390297},"publisher-location":"Cham","reference-count":28,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319060880"},{"type":"electronic","value":"9783319060897"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2014]]},"DOI":"10.1007\/978-3-319-06089-7_15","type":"book-chapter","created":{"date-parts":[[2014,4,1]],"date-time":"2014-04-01T01:55:10Z","timestamp":1396317310000},"page":"216-228","source":"Crossref","is-referenced-by-count":0,"title":["Polynomial-Time Algorithms for Subgraph Isomorphism in Small Graph Classes of Perfect Graphs"],"prefix":"10.1007","author":[{"given":"Matsuo","family":"Konagaya","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yota","family":"Otachi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ryuhei","family":"Uehara","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"15_CR1","doi-asserted-by":"publisher","first-page":"999","DOI":"10.1016\/j.dam.2011.12.012","volume":"160","author":"R. Belmonte","year":"2012","unstructured":"Belmonte, R., Heggernes, P., van \u2019t Hof, P.: Edge contractions in subclasses of chordal graphs. Discrete Appl. Math.\u00a0160, 999\u20131010 (2012)","journal-title":"Discrete Appl. Math."},{"key":"15_CR2","doi-asserted-by":"crossref","unstructured":"Blair, J.R.S., Peyton, B.: An introduction to chordal graphs and clique trees. In: George, A., Gilbert, J.R., Liu, J.W.H. (eds.) Graph Theory and Sparse Matrix Computation. The IMA Volumes in Mathematics and its Applications, vol.\u00a056, pp. 1\u201329. Springer (1993)","DOI":"10.1007\/978-1-4613-8369-7_1"},{"key":"15_CR3","doi-asserted-by":"crossref","unstructured":"Brandst\u00e4dt, A., Le, V.B., Spinrad, J.P.: Graph Classes: A Survey. SIAM (1999)","DOI":"10.1137\/1.9780898719796"},{"key":"15_CR4","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1002\/net.3230110103","volume":"11","author":"C.J. Colbourn","year":"1981","unstructured":"Colbourn, C.J.: On testing isomorphism of permutation graphs. Networks\u00a011, 13\u201321 (1981)","journal-title":"Networks"},{"key":"15_CR5","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":"15_CR6","unstructured":"Dorn, F.: Planar subgraph isomorphism revisited. In: STACS 2010. LIPIcs, vol.\u00a05, pp. 263\u2013274 (2010)"},{"key":"15_CR7","doi-asserted-by":"publisher","first-page":"1","DOI":"10.7155\/jgaa.00014","volume":"3","author":"D. Eppstein","year":"1999","unstructured":"Eppstein, D.: Subgraph isomorphism in planar graphs and related problems. J. Graph Algorithms Appl.\u00a03, 1\u201327 (1999)","journal-title":"J. Graph Algorithms Appl."},{"key":"15_CR8","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman and Company (1979)"},{"key":"15_CR9","doi-asserted-by":"crossref","unstructured":"Golumbic, M.C.: Algorithmic Graph Theory and Perfect Graphs, 2nd edn. Annals of Discrete Mathematics, vol.\u00a057. North Holland (2004)","DOI":"10.1016\/S0167-5060(04)80059-1"},{"key":"15_CR10","doi-asserted-by":"publisher","first-page":"169","DOI":"10.1007\/BF02579273","volume":"1","author":"M. Gr\u00f6tschel","year":"1981","unstructured":"Gr\u00f6tschel, M., Lov\u00e1sz, L., Schrijver, A.: The ellipsoid method and its consequences in combinatorial optimization. Combinatorica\u00a01, 169\u2013197 (1981)","journal-title":"Combinatorica"},{"key":"15_CR11","doi-asserted-by":"publisher","first-page":"287","DOI":"10.1016\/0304-3975(96)00046-1","volume":"164","author":"A. Gupta","year":"1996","unstructured":"Gupta, A., Nishimura, N.: The complexity of subgraph isomorphism for classes of partial k-trees. Theoret. Comput. Sci.\u00a0164, 287\u2013298 (1996)","journal-title":"Theoret. Comput. Sci."},{"key":"15_CR12","unstructured":"Heggernes, P.: Treewidth, partial k-trees, and chordal graphs. Partial curriculum in INF334 - Advanced algorithmical techniques, Department of Informatics, University of Bergen, Norway (2005)"},{"key":"15_CR13","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 J. Comput.\u00a014, 87\u2013108 (2007)","journal-title":"Nordic J. Comput."},{"key":"15_CR14","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":"15_CR15","unstructured":"Heggernes, P., van \u2019t Hof, P., Meister, D., Villanger, Y.: Induced subgraph isomorphism on proper interval and bipartite permutation graphs. Submitted manuscript"},{"key":"15_CR16","doi-asserted-by":"publisher","first-page":"3164","DOI":"10.1016\/j.disc.2012.07.010","volume":"312","author":"S. Kijima","year":"2012","unstructured":"Kijima, S., Otachi, Y., Saitoh, T., Uno, T.: Subgraph isomorphism in graph classes. Discrete Math.\u00a0312, 3164\u20133173 (2012)","journal-title":"Discrete Math."},{"key":"15_CR17","doi-asserted-by":"publisher","first-page":"295","DOI":"10.1016\/0304-3975(89)90011-X","volume":"63","author":"A. Lingas","year":"1989","unstructured":"Lingas, A.: Subgraph isomorphism for biconnected outerplanar graphs in cubic time. Theoret. Comput. Sci.\u00a063, 295\u2013302 (1989)","journal-title":"Theoret. Comput. Sci."},{"key":"15_CR18","doi-asserted-by":"publisher","first-page":"183","DOI":"10.1145\/322123.322125","volume":"26","author":"G.S. Lueker","year":"1979","unstructured":"Lueker, G.S., Booth, K.S.: A linear time algorithm for deciding interval graph isomorphism. J. ACM\u00a026, 183\u2013195 (1979)","journal-title":"J. ACM"},{"key":"15_CR19","unstructured":"Marx, D., Pilipczuk, M.: Everything you always wanted to know about the parameterized complexity of subgraph isomorphism (but were afraid to ask). CoRR, abs\/1307.2187 (2013)"},{"key":"15_CR20","doi-asserted-by":"publisher","first-page":"275","DOI":"10.1007\/s00453-011-9588-0","volume":"65","author":"D. Marx","year":"2013","unstructured":"Marx, D., Schlotter, I.: Cleaning interval graphs. Algorithmica\u00a065, 275\u2013316 (2013)","journal-title":"Algorithmica"},{"key":"15_CR21","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 Math.\u00a0108, 343\u2013364 (1992)","journal-title":"Discrete Math."},{"key":"15_CR22","doi-asserted-by":"crossref","unstructured":"Matula, D.W.: Subtree isomorphism in O(n\n                  5\/2). In: Alspach, B., Hell, P., Miller, D. (eds.) Algorithmic Aspects of Combinatorics. Annals of Discrete Mathematics, vol.\u00a02, pp. 91\u2013106. Elsevier (1978)","DOI":"10.1016\/S0167-5060(08)70324-8"},{"issue":"2","key":"15_CR23","doi-asserted-by":"publisher","first-page":"311","DOI":"10.1007\/s00453-010-9486-x","volume":"64","author":"D. Nussbaum","year":"2012","unstructured":"Nussbaum, D., Pu, S., Sack, J.-R., Uno, T., Zarrabi-Zadeh, H.: Finding maximum edge bicliques in convex bipartite graphs. Algorithmica\u00a064(2), 311\u2013325 (2012)","journal-title":"Algorithmica"},{"key":"15_CR24","doi-asserted-by":"publisher","first-page":"651","DOI":"10.1016\/S0166-218X(03)00333-0","volume":"131","author":"R. Peeters","year":"2003","unstructured":"Peeters, R.: The maximum edge biclique problem is NP-complete. Discrete Appl. Math.\u00a0131, 651\u2013654 (2003)","journal-title":"Discrete Appl. Math."},{"key":"15_CR25","doi-asserted-by":"crossref","unstructured":"Spinrad, J.P.: Efficient Graph Representations. Fields Institute monographs, vol.\u00a019. American Mathematical Society (2003)","DOI":"10.1090\/fim\/019"},{"key":"15_CR26","doi-asserted-by":"publisher","first-page":"91","DOI":"10.1016\/0304-3975(82)90133-5","volume":"17","author":"M.M. Sys\u0142o","year":"1982","unstructured":"Sys\u0142o, M.M.: The subgraph isomorphism problem for outerplanar graphs. Theoret. Comput. Sci.\u00a017, 91\u201397 (1982)","journal-title":"Theoret. Comput. Sci."},{"key":"15_CR27","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. Proc. Amer. Math. Soc.\u00a016, 17\u201320 (1965)","journal-title":"Proc. Amer. Math. Soc."},{"issue":"3","key":"15_CR28","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 Appl. Math.\u00a069(3), 247\u2013255 (1996)","journal-title":"Discrete Appl. Math."}],"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-319-06089-7_15","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,26]],"date-time":"2019-05-26T13:30:09Z","timestamp":1558877409000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-06089-7_15"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014]]},"ISBN":["9783319060880","9783319060897"],"references-count":28,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-06089-7_15","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2014]]}}}