{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,26]],"date-time":"2025-03-26T15:03:38Z","timestamp":1743001418363,"version":"3.40.3"},"publisher-location":"Cham","reference-count":17,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319193144"},{"type":"electronic","value":"9783319193151"}],"license":[{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2015]]},"DOI":"10.1007\/978-3-319-19315-1_1","type":"book-chapter","created":{"date-parts":[[2015,6,6]],"date-time":"2015-06-06T10:42:08Z","timestamp":1433587328000},"page":"1-12","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["On the Complexity of Various Parameterizations of Common Induced Subgraph Isomorphism"],"prefix":"10.1007","author":[{"given":"Faisal N.","family":"Abu-Khzam","sequence":"first","affiliation":[]},{"given":"\u00c9douard","family":"Bonnet","sequence":"additional","affiliation":[]},{"given":"Florian","family":"Sikora","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2015,6,7]]},"reference":[{"issue":"3","key":"1_CR1","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1016\/j.ipl.2013.11.007","volume":"114","author":"FN Abu-Khzam","year":"2014","unstructured":"Abu-Khzam, F.N.: Maximum common induced subgraph parameterized by vertex cover. Inf. Process. Lett. 114(3), 99\u2013103 (2014)","journal-title":"Inf. Process. Lett."},{"issue":"1","key":"1_CR2","first-page":"95","volume":"75","author":"T Akutsu","year":"1992","unstructured":"Akutsu, T.: An RNC algorithm for finding a largest common subtree of two trees. IEICE Trans. Inf. Syst. 75(1), 95\u2013101 (1992)","journal-title":"IEICE Trans. Inf. Syst."},{"issue":"9","key":"1_CR3","first-page":"1488","volume":"76","author":"T Akutsu","year":"1993","unstructured":"Akutsu, T.: A polynomial time algorithm for finding a largest common subgraph of almost trees of bounded degree. IEICE Trans. Fundam. Electron. Commun. Comput. Sci. 76(9), 1488\u20131493 (1993)","journal-title":"IEICE Trans. Fundam. Electron. Commun. Comput. Sci."},{"issue":"1","key":"1_CR4","doi-asserted-by":"publisher","first-page":"277","DOI":"10.1137\/120880240","volume":"28","author":"HL Bodlaender","year":"2014","unstructured":"Bodlaender, H.L., Jansen, B.M.P., Kratsch, S.: Kernelization lower bounds by cross-composition. SIAM J. Discrete Math. 28(1), 277\u2013305 (2014)","journal-title":"SIAM J. Discrete Math."},{"issue":"4","key":"1_CR5","doi-asserted-by":"publisher","first-page":"654","DOI":"10.1016\/S0022-0000(03)00073-4","volume":"67","author":"M Cesati","year":"2003","unstructured":"Cesati, M.: The turing way to parameterized complexity. J. Comput. Syst. Sci. 67(4), 654\u2013685 (2003)","journal-title":"J. Comput. Syst. Sci."},{"issue":"40\u201342","key":"1_CR6","doi-asserted-by":"publisher","first-page":"3736","DOI":"10.1016\/j.tcs.2010.06.026","volume":"411","author":"J Chen","year":"2010","unstructured":"Chen, J., Kanj, I.A., Xia, G.: Improved upper bounds for vertex cover. Theor. Comput. Sci. 411(40\u201342), 3736\u20133756 (2010)","journal-title":"Theor. Comput. Sci."},{"key":"1_CR7","series-title":"Texts in Computer Science","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4471-5559-1","volume-title":"Fundamentals of Parameterized Complexity","author":"RG Downey","year":"2013","unstructured":"Downey, R.G., Fellows, M.R.: Fundamentals of Parameterized Complexity. Texts in Computer Science. Springer, London (2013)"},{"issue":"3","key":"1_CR8","doi-asserted-by":"publisher","first-page":"541","DOI":"10.1016\/j.ejc.2012.04.008","volume":"34","author":"MR Fellows","year":"2013","unstructured":"Fellows, M.R., Jansen, B.M.P., Rosamond, F.A.: Towards fully multivariate algorithmics: parameter ecology and the deconstruction of computational complexity. Eur. J. Comb. 34(3), 541\u2013566 (2013)","journal-title":"Eur. J. Comb."},{"issue":"1","key":"1_CR9","doi-asserted-by":"publisher","first-page":"113","DOI":"10.1137\/S0097539799360768","volume":"31","author":"J Flum","year":"2001","unstructured":"Flum, J., Grohe, M.: Fixed-parameter tractability, definability, and model-checking. SIAM J. Comput. 31(1), 113\u2013145 (2001)","journal-title":"SIAM J. Comput."},{"key":"1_CR10","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"MR Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman, San Francisco (1979)"},{"issue":"3","key":"1_CR11","doi-asserted-by":"publisher","first-page":"707","DOI":"10.1006\/jmbi.1993.1074","volume":"229","author":"HM Grindley","year":"1993","unstructured":"Grindley, H.M., Artymiuk, P.J., Rice, D.W., Willett, P.: Identification of tertiary structure resemblance in proteins using a maximal common subgraph isomorphism algorithm. J. Mol. Biol. 229(3), 707\u2013721 (1993)","journal-title":"J. Mol. Biol."},{"issue":"2","key":"1_CR12","doi-asserted-by":"publisher","first-page":"289","DOI":"10.1089\/cmb.1996.3.289","volume":"3","author":"I Koch","year":"1996","unstructured":"Koch, I., Lengauer, T., Wanke, E.: An algorithm for finding maximal common subtopologies in a set of protein structures. J. Comput. Biol. 3(2), 289\u2013306 (1996)","journal-title":"J. Comput. Biol."},{"key":"1_CR13","doi-asserted-by":"publisher","first-page":"137","DOI":"10.1021\/ci00031a005","volume":"21","author":"J McGregor","year":"1981","unstructured":"McGregor, J., Willett, P.: Use of a maximal common subgraph algorithm in the automatic identification of the ostensible bond changes occurring in chemical reactions. J. Chem. Inf. Comput. Sci 21, 137\u2013140 (1981)","journal-title":"J. Chem. Inf. Comput. Sci"},{"issue":"4","key":"1_CR14","doi-asserted-by":"publisher","first-page":"715","DOI":"10.1016\/j.dam.2008.07.011","volume":"157","author":"H Moser","year":"2009","unstructured":"Moser, H., Sikdar, S.: The parameterized complexity of the induced matching problem. Discrete Appl. Math. 157(4), 715\u2013727 (2009)","journal-title":"Discrete Appl. Math."},{"key":"1_CR15","series-title":"Lecture Series in Mathematics and Its Applications","doi-asserted-by":"publisher","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. Lecture Series in Mathematics and Its Applications. Oxford University Press, Oxford (2006)"},{"key":"1_CR16","doi-asserted-by":"publisher","first-page":"521","DOI":"10.1023\/A:1021271615909","volume":"16","author":"JW Raymond","year":"2002","unstructured":"Raymond, J.W., Willett, P.: Maximum common subgraph isomorphism algorithms for the matching of chemical structures. J. Comput. Aided Mol. Des. 16, 521\u2013533 (2002)","journal-title":"J. Comput. Aided Mol. Des."},{"issue":"2","key":"1_CR17","doi-asserted-by":"publisher","first-page":"57","DOI":"10.1016\/j.ipl.2004.06.019","volume":"92","author":"A Yamaguchi","year":"2004","unstructured":"Yamaguchi, A., Aoki, K.F., Mamitsuka, H.: Finding the maximum common subgraph of a partial k-tree and a graph with a polynomially bounded number of spanning trees. Inf. Process. Lett. 92(2), 57\u201363 (2004)","journal-title":"Inf. Process. Lett."}],"container-title":["Lecture Notes in Computer Science","Combinatorial Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-19315-1_1","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,2,8]],"date-time":"2023-02-08T12:25:31Z","timestamp":1675859131000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-319-19315-1_1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015]]},"ISBN":["9783319193144","9783319193151"],"references-count":17,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-19315-1_1","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2015]]},"assertion":[{"value":"7 June 2015","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}