{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,2]],"date-time":"2025-12-02T15:22:06Z","timestamp":1764688926232,"version":"build-2065373602"},"reference-count":23,"publisher":"MDPI AG","issue":"1","license":[{"start":{"date-parts":[[2013,2,18]],"date-time":"2013-02-18T00:00:00Z","timestamp":1361145600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/3.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>The maximum common connected edge subgraph problem is to find a connected graph with the maximum number of edges that is isomorphic to a subgraph of each of the two input graphs, where it has applications in pattern recognition and chemistry. This paper presents a dynamic programming algorithm for the problem when the two input graphs are outerplanar graphs of a bounded vertex degree, where it is known that the problem is NP-hard, even for outerplanar graphs of an unbounded degree. Although the algorithm repeatedly modifies input graphs, it is shown that the number of relevant subproblems is polynomially bounded, and thus, the algorithm works in polynomial time.<\/jats:p>","DOI":"10.3390\/a6010119","type":"journal-article","created":{"date-parts":[[2013,2,19]],"date-time":"2013-02-19T11:11:16Z","timestamp":1361272276000},"page":"119-135","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":13,"title":["A Polynomial-Time Algorithm for Computing the Maximum Common Connected Edge Subgraph of Outerplanar Graphs of Bounded Degree"],"prefix":"10.3390","volume":"6","author":[{"given":"Tatsuya","family":"Akutsu","sequence":"first","affiliation":[{"name":"Bioinformatics Center, Institute for Chemical Research, Kyoto University, Gokasho, Uji, Kyoto 611-0011, Japan"}]},{"given":"Takeyuki","family":"Tamura","sequence":"additional","affiliation":[{"name":"Bioinformatics Center, Institute for Chemical Research, Kyoto University, Gokasho, Uji, Kyoto 611-0011, Japan"}]}],"member":"1968","published-online":{"date-parts":[[2013,2,18]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"265","DOI":"10.1142\/S0218001404003228","article-title":"Thirty years of graph matching in pattern recognition","volume":"18","author":"Conte","year":"2004","journal-title":"Int. J. Pattern Recognit. Artif. Intell."},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"1075","DOI":"10.1016\/S0031-3203(00)00048-0","article-title":"Video indexing and similarity retrieval by largest common subgraph detection using decision trees","volume":"34","author":"Shearer","year":"2001","journal-title":"Pattern Recognit."},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"521","DOI":"10.1023\/A:1021271615909","article-title":"Maximum common subgraph isomorphism algorithms for the matching of chemical structures","volume":"16","author":"Raymond","year":"2002","journal-title":"J. Comput. Aided Mol. Des."},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"68","DOI":"10.1002\/wcms.5","article-title":"Maximum common subgraph isomorphism algorithms and their applications in molecular science: A review","volume":"1","author":"Rarey","year":"2011","journal-title":"WIREs Comput. Mol. Sci."},{"key":"ref_5","unstructured":"Abu-Khzam, F.N., Samatova, N.F., Rizk, M.A., and Langston, M.A. (2007). Proceedings of the 2007 IEEE\/ACS International Conference Computer Systems and Applications, IEEE."},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"S6:1","DOI":"10.1186\/1471-2105-7-S4-S6","article-title":"Maximum common subgraph: Some upper bound and lower bound results","volume":"7","author":"Huang","year":"2006","journal-title":"BMC Bioinforma."},{"key":"ref_7","first-page":"377","article-title":"On the Approximability of the Maximum Common Subgraph Problem","volume":"Volume 577","author":"Kann","year":"1992","journal-title":"Proceedings of the 9th Symposium Theoretical Aspects of Computer Science"},{"key":"ref_8","unstructured":"Garey, M.R., and Johnson, D.S. (1979). Computers and Intractability, Freeman."},{"key":"ref_9","first-page":"1488","article-title":"A polynomial time algorithm for finding a largest common subgraph of almost trees of bounded degree","volume":"E76-A","author":"Akutsu","year":"1993","journal-title":"IEICE Trans. Fundam."},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"57","DOI":"10.1016\/j.ipl.2004.06.019","article-title":"Finding the maximum common subgraph of a partial k-tree and a graph with a polynomially bounded number of spanning trees","volume":"92","author":"Yamaguchi","year":"2004","journal-title":"Inf. Proc. Lett."},{"key":"ref_11","unstructured":"Schietgat, L., Ramon, J., and Bruynooghe, M. (2007, January 1). A Polynomial-Time Metric for Outerplanar Graphs. Proceedings of the Workshop on Mining and Learning with Graphs, Firenze, Italy."},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"215","DOI":"10.7155\/jgaa.00090","article-title":"Computing and drawing isomorphic subgraphs","volume":"8","author":"Bachl","year":"2004","journal-title":"J. Graph Algorithms Appl."},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"295","DOI":"10.1016\/0304-3975(89)90011-X","article-title":"Subgraph isomorphism for biconnected outerplanar graphs in cubic time","volume":"63","author":"Lingas","year":"1989","journal-title":"Theoret. Comput. Sci."},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"91","DOI":"10.1016\/0304-3975(82)90133-5","article-title":"The subgraph isomorphism problem for outerplanar graphs","volume":"17","author":"Syslo","year":"1982","journal-title":"Theoret. Comput. Sci."},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"337","DOI":"10.1007\/s004530010023","article-title":"Faster algorithms for subgraph isomorphism of k-connected partial k-trees","volume":"27","author":"Dessmark","year":"2000","journal-title":"Algorithmica"},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"755","DOI":"10.1016\/j.jcss.2007.01.003","article-title":"Subgraph isomorphism, log-bounded fragmentation, and graphs of (locally) bounded treewidth","volume":"73","author":"Hajiaghayi","year":"2007","journal-title":"J. Comput. Syst. Sci."},{"key":"ref_17","first-page":"76","article-title":"A Polynomial-Time Algorithm for Computing the Maximum Common Subgraph of Outerplanar Graphs of Bounded Degree","volume":"Volume 7464","author":"Akutsu","year":"2012","journal-title":"Proceedings of the 37th International Symposium on Mathematical Foundations of Computer Science"},{"key":"ref_18","unstructured":"Horv\u00e1th, T., Ramon, J., and Wrobel, S. (2006). Proceedings of the 12th ACM SIGKDD Int. Conf. Knowledge Discovery and Data Mining, ACM."},{"key":"ref_19","first-page":"95","article-title":"An RNC algorithm for finding a largest common subtree of two trees","volume":"E75-D","author":"Akutsu","year":"1992","journal-title":"IEICE Trans. Inf. Syst."},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"47","DOI":"10.1016\/0012-365X(79)90060-8","article-title":"Characterizations of outerplanar graphs","volume":"26","author":"Syslo","year":"1979","journal-title":"Disc. Math."},{"key":"ref_21","doi-asserted-by":"crossref","unstructured":"Chartrand, G., Lesniak, L., and Zhang, P. (2010). Graphs and Digraphs, Fifth Edition, Chapman and Hall\/CRC.","DOI":"10.1201\/b14892"},{"key":"ref_22","unstructured":"Cormen, T.H., Leiserson, C.E., Rivest, R.L., and Stein, C. (2009). Introduction to Algorithms, Third Edition, The MIT Press."},{"key":"ref_23","first-page":"146","article-title":"On the Complexity of the Maximum Common Subgraph Problem for Partial k-trees of Bounded Degree","volume":"Volume 7676","author":"Akutsu","year":"2012","journal-title":"Proceedings of the 23rd International Symposium Algorithms and Computation"}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/6\/1\/119\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T21:44:58Z","timestamp":1760219098000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/6\/1\/119"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,2,18]]},"references-count":23,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2013,3]]}},"alternative-id":["a6010119"],"URL":"https:\/\/doi.org\/10.3390\/a6010119","relation":{},"ISSN":["1999-4893"],"issn-type":[{"type":"electronic","value":"1999-4893"}],"subject":[],"published":{"date-parts":[[2013,2,18]]}}}