{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,5]],"date-time":"2026-02-05T05:31:07Z","timestamp":1770269467151,"version":"3.49.0"},"publisher-location":"Berlin, Heidelberg","reference-count":22,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783642352607","type":"print"},{"value":"9783642352614","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2012]]},"DOI":"10.1007\/978-3-642-35261-4_18","type":"book-chapter","created":{"date-parts":[[2012,12,14]],"date-time":"2012-12-14T01:59:41Z","timestamp":1355450381000},"page":"146-155","source":"Crossref","is-referenced-by-count":5,"title":["On the Complexity of the Maximum Common Subgraph Problem for Partial k-Trees of Bounded Degree"],"prefix":"10.1007","author":[{"given":"Tatsuya","family":"Akutsu","sequence":"first","affiliation":[]},{"given":"Takeyuki","family":"Tamura","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"18_CR1","doi-asserted-by":"crossref","unstructured":"Abu-Khzam, F.N., Samatova, N.F., Rizk, M.A., Langston, M.A.: The maximum common subgraph problem: faster solutions via vertex cover. In: Proc. 2007 IEEE\/ACS Int. Conf. Computer Systems and Applications, pp. 367\u2013373. IEEE (2007)","DOI":"10.1109\/AICCSA.2007.370907"},{"key":"18_CR2","first-page":"1488","volume":"E76-A","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. Fundamentals\u00a0E76-A, 1488\u20131493 (1993)","journal-title":"IEICE Trans. Fundamentals"},{"key":"18_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"76","DOI":"10.1007\/978-3-642-32589-2_10","volume-title":"Mathematical Foundations of Computer Science 2012","author":"T. Akutsu","year":"2012","unstructured":"Akutsu, T., Tamura, T.: A Polynomial-Time Algorithm for Computing the Maximum Common Subgraph of Outerplanar Graphs of Bounded Degree. In: Rovan, B., Sassone, V., Widmayer, P. (eds.) MFCS 2012. LNCS, vol.\u00a07464, pp. 76\u201387. Springer, Heidelberg (2012)"},{"key":"18_CR4","doi-asserted-by":"crossref","unstructured":"Babai, L.: Luks. E. M.: Canonical labeling of graphs. In: Proc. 15th ACM Symp. Theory of Computing, pp. 171\u2013183. ACM Press (1983)","DOI":"10.1145\/800061.808746"},{"key":"18_CR5","doi-asserted-by":"publisher","first-page":"215","DOI":"10.7155\/jgaa.00090","volume":"8","author":"S. Bachl","year":"2004","unstructured":"Bachl, S., Brandenburg, F.-J., Gmach, D.: Computing and drawing isomorphic subgraphs. J. Graph Algorithms and Applications\u00a08, 215\u2013238 (2004)","journal-title":"J. Graph Algorithms and Applications"},{"key":"18_CR6","doi-asserted-by":"publisher","first-page":"265","DOI":"10.1142\/S0218001404003228","volume":"18","author":"D. Conte","year":"2004","unstructured":"Conte, D., Foggia, P., Sansone, C., Vento, M.: Thirty years of graph matching in pattern recognition. Int. J. Pattern Recognition and Artificial Intelligence\u00a018, 265\u2013298 (2004)","journal-title":"Int. J. Pattern Recognition and Artificial Intelligence"},{"key":"18_CR7","volume-title":"Parameterized Complexity Theory","author":"J. Flum","year":"2006","unstructured":"Flum, J., Grohe, M.: Parameterized Complexity Theory. Springer, Berlin (2006)"},{"key":"18_CR8","volume-title":"Computers and Intractability","author":"M.R. Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability. Freeman, New York (1979)"},{"key":"18_CR9","doi-asserted-by":"publisher","first-page":"755","DOI":"10.1016\/j.jcss.2007.01.003","volume":"73","author":"M. Hajiaghayi","year":"2007","unstructured":"Hajiaghayi, M., Nishimura, N.: Subgraph isomorphism, log-bounded fragmentation and graphs of (locally) bounded treewidth. J. Comput. Syst. Sci.\u00a073, 755\u2013768 (2007)","journal-title":"J. Comput. Syst. Sci."},{"key":"18_CR10","doi-asserted-by":"publisher","first-page":"2784","DOI":"10.1016\/j.tcs.2010.03.030","volume":"411","author":"T. Horv\u00e1th","year":"2010","unstructured":"Horv\u00e1th, T., Ramon, J.: Efficient frequent connected subgraph mining in graphs of bounded tree-width. Theoret. Comput. Sci.\u00a0411, 2784\u20132797 (2010)","journal-title":"Theoret. Comput. Sci."},{"issue":"4","key":"18_CR11","first-page":"S","volume":"7","author":"X. Huang","year":"2006","unstructured":"Huang, X., Lai, J., Jennings, S.F.: Maximum common subgraph: some upper bound and lower bound results. BMC Bioinformatics 7(suppl. 4), S-4 (2006)","journal-title":"BMC Bioinformatics"},{"key":"18_CR12","doi-asserted-by":"publisher","first-page":"1122","DOI":"10.1137\/S009753979223842X","volume":"24","author":"T. Jiang","year":"1995","unstructured":"Jiang, T., Li, M.: On the approximation of shortest common supersequences and longest common subsequences. SIAM J. Comput.\u00a024, 1122\u20131139 (1995)","journal-title":"SIAM J. Comput."},{"key":"18_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"375","DOI":"10.1007\/3-540-55210-3_198","volume-title":"STACS 92","author":"V. Kann","year":"1992","unstructured":"Kann, V.: On the Approximability of the Maximum Common Subgraph Problem. In: Finkel, A., Jantzen, M. (eds.) STACS 1992. LNCS, vol.\u00a0577, pp. 375\u2013388. Springer, Heidelberg (1992)"},{"key":"18_CR14","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":"18_CR15","doi-asserted-by":"publisher","first-page":"42","DOI":"10.1016\/0022-0000(82)90009-5","volume":"25","author":"E.M. Luks","year":"1982","unstructured":"Luks, E.M.: Isomorphism of graphs of bounded valence can be tested in polynomial time. J. Comput. Syst. Sci.\u00a025, 42\u201365 (1982)","journal-title":"J. Comput. Syst. Sci."},{"key":"18_CR16","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":"18_CR17","doi-asserted-by":"publisher","first-page":"521","DOI":"10.1023\/A:1021271615909","volume":"16","author":"J.W. Raymond","year":"2002","unstructured":"Raymond, J.W., Willett, P.: Maximum common subgraph isomorphism algorithms for the matching of chemical structures. J. Computer-Aided Molecular Design\u00a016, 521\u2013533 (2002)","journal-title":"J. Computer-Aided Molecular Design"},{"key":"18_CR18","unstructured":"Schietgat, L., Ramon, J., Bruynooghe, M.: A polynomial-time metric for outerplanar graphs. In: Proc. Workshop on Mining and Learning with Graphs (2007)"},{"key":"18_CR19","doi-asserted-by":"publisher","first-page":"1075","DOI":"10.1016\/S0031-3203(00)00048-0","volume":"34","author":"K. Shearer","year":"2001","unstructured":"Shearer, K., Bunke, H., Venkatesh, S.: Video indexing and similarity retrieval by largest common subgraph detection using decision trees. Pattern Recognition\u00a034, 1075\u20131091 (2001)","journal-title":"Pattern Recognition"},{"key":"18_CR20","doi-asserted-by":"publisher","first-page":"91","DOI":"10.1016\/0304-3975(82)90133-5","volume":"17","author":"M.M. Syslo","year":"1982","unstructured":"Syslo, M.M.: The subgraph isomorphism problem for outerplanar graphs. Theoret. Comput. Sci.\u00a017, 91\u201397 (1982)","journal-title":"Theoret. Comput. Sci."},{"key":"18_CR21","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. Proc. Lett.\u00a092, 57\u201363 (2004)","journal-title":"Inf. Proc. Lett."},{"key":"18_CR22","doi-asserted-by":"publisher","first-page":"1426","DOI":"10.1007\/BF02104746","volume":"29","author":"V.M. Zemlyachenko","year":"1985","unstructured":"Zemlyachenko, V.M., Kornienko, N.M., Tyshkevich, R.I.: Graph isomorphism problem. J. Soviet Math.\u00a029, 1426\u20131481 (1985)","journal-title":"J. Soviet Math."}],"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-35261-4_18","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,7,7]],"date-time":"2019-07-07T02:25:25Z","timestamp":1562466325000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-35261-4_18"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012]]},"ISBN":["9783642352607","9783642352614"],"references-count":22,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-35261-4_18","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012]]}}}