{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:32:06Z","timestamp":1759638726372,"version":"3.37.3"},"reference-count":35,"publisher":"Springer Science and Business Media LLC","issue":"7","license":[{"start":{"date-parts":[[2020,2,14]],"date-time":"2020-02-14T00:00:00Z","timestamp":1581638400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2020,2,14]],"date-time":"2020-02-14T00:00:00Z","timestamp":1581638400000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2020,7]]},"DOI":"10.1007\/s00453-020-00685-8","type":"journal-article","created":{"date-parts":[[2020,2,14]],"date-time":"2020-02-14T09:02:54Z","timestamp":1581670974000},"page":"2039-2062","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["The Generalized Definitions of the Two-Dimensional Largest Common Substructure Problems"],"prefix":"10.1007","volume":"82","author":[{"given":"Huang-Ting","family":"Chan","sequence":"first","affiliation":[]},{"given":"Hsuan-Tsung","family":"Chiu","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6643-5523","authenticated-orcid":false,"given":"Chang-Biau","family":"Yang","sequence":"additional","affiliation":[]},{"given":"Yung-Hsing","family":"Peng","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2020,2,14]]},"reference":[{"issue":"1\u20132","key":"685_CR1","doi-asserted-by":"crossref","first-page":"181","DOI":"10.1016\/0304-3975(94)00254-G","volume":"147","author":"E Amaldi","year":"1995","unstructured":"Amaldi, E., Kann, V.: The complexity and approximability of finding maximum feasible subsystems of linear relations. Theor. Comput. Sci. 147(1\u20132), 181\u2013210 (1995)","journal-title":"Theor. Comput. Sci."},{"issue":"3","key":"685_CR2","doi-asserted-by":"crossref","first-page":"438","DOI":"10.1016\/j.tcs.2008.08.037","volume":"409","author":"A Amir","year":"2008","unstructured":"Amir, A., Hartman, T., Kapah, O., Shalom, B.R., Tsur, D.: Generalized LCS. Theor. Comput. Sci. 409(3), 438\u2013449 (2008)","journal-title":"Theor. Comput. Sci."},{"issue":"6","key":"685_CR3","doi-asserted-by":"crossref","first-page":"360","DOI":"10.1016\/j.ipl.2008.07.005","volume":"108","author":"HY Ann","year":"2008","unstructured":"Ann, H.Y., Yang, C.B., Tseng, C.T., Hor, C.Y.: A fast and simple algorithm for computing the longest common subsequence of run-length encoded strings. Inf. Process. Lett. 108(6), 360\u2013364 (2008)","journal-title":"Inf. Process. Lett."},{"issue":"5","key":"685_CR4","doi-asserted-by":"crossref","first-page":"753","DOI":"10.1145\/290179.290180","volume":"45","author":"S Arora","year":"1998","unstructured":"Arora, S.: Polynomial time approximation schemes for euclidean traveling salesman and other geometric problems. JACM 45(5), 753\u2013782 (1998)","journal-title":"JACM"},{"key":"685_CR5","volume-title":"Complexity and Approximation: Combinatorial Optimization Problems and Their Approximability Properties","author":"G Ausiello","year":"2012","unstructured":"Ausiello, G., Crescenzi, P., Gambosi, G., Kann, V., Marchetti-Spaccamela, A., Protasi, M.: Complexity and Approximation: Combinatorial Optimization Problems and Their Approximability Properties. Springer, Berlin (2012)"},{"key":"685_CR6","doi-asserted-by":"crossref","unstructured":"Baeza-Yates, R.A.: Similarity in two-dimensional strings. In: International Computing and Combinatorics Conference, pp. 319\u2013328. Springer, Berlin (1998)","DOI":"10.1007\/3-540-68535-9_36"},{"issue":"5","key":"685_CR7","doi-asserted-by":"crossref","first-page":"168","DOI":"10.1016\/0020-0190(77)90017-5","volume":"6","author":"RS Bird","year":"1977","unstructured":"Bird, R.S.: Two dimensional pattern matching. Inf. Process. Lett. 6(5), 168\u2013170 (1977)","journal-title":"Inf. Process. Lett."},{"key":"685_CR8","volume-title":"Introduction to Protein Structure","author":"CI Branden","year":"1999","unstructured":"Branden, C.I., et al.: Introduction to Protein Structure. Garland Science, New York (1999)"},{"key":"685_CR9","unstructured":"Chang, S., Li, Y.: Representation of multi-resolution symbolic and binary pictures using 2D H-strings. In: IEEE Workshop on Languages for Automation: Symbiotic and Intelligent Robots, 1988, pp. 190\u2013195. IEEE (1988)"},{"key":"685_CR10","doi-asserted-by":"crossref","unstructured":"Chang, S.K., Jungert, E., Li, Y.: Representation and retrieval of symbolic pictures using generalized 2D strings. In: 1989 Symposium on Visual Communications, Image Processing, and Intelligent Robotics Systems, pp. 1360\u20131372. International Society for Optics and Photonics (1989)","DOI":"10.1117\/12.970145"},{"key":"685_CR11","doi-asserted-by":"crossref","first-page":"413","DOI":"10.1109\/TPAMI.1987.4767923","volume":"3","author":"SK Chang","year":"1987","unstructured":"Chang, S.K., Shi, Q.Y., Yan, C.W.: Iconic indexing by 2-D strings. IEEE Trans. Pattern Anal. Mach. Intell. 3, 413\u2013428 (1987)","journal-title":"IEEE Trans. Pattern Anal. Mach. Intell."},{"issue":"5","key":"685_CR12","doi-asserted-by":"crossref","first-page":"681","DOI":"10.1109\/32.6147","volume":"14","author":"SK Chang","year":"1988","unstructured":"Chang, S.K., Yan, C., Dimitroff, D.C., Arndt, T.: An intelligent image database system. IEEE Trans. Softw. Eng. 14(5), 681\u2013688 (1988)","journal-title":"IEEE Trans. Softw. Eng."},{"key":"685_CR13","doi-asserted-by":"crossref","unstructured":"Cook, S.A.: The complexity of theorem-proving procedures. In: Proceedings of the 3rd Annual ACM Symposium on Theory of Computing, pp. 151\u2013158. ACM (1971)","DOI":"10.1145\/800157.805047"},{"issue":"2","key":"685_CR14","doi-asserted-by":"crossref","first-page":"241","DOI":"10.1016\/0890-5401(91)90025-W","volume":"93","author":"P Crescenzi","year":"1991","unstructured":"Crescenzi, P., Panconesi, A.: Completeness in approximation classes. Inf. Comput. 93(2), 241\u2013262 (1991)","journal-title":"Inf. Comput."},{"issue":"1","key":"685_CR15","doi-asserted-by":"crossref","first-page":"45","DOI":"10.1016\/0020-0190(94)90139-2","volume":"52","author":"G Galbiati","year":"1994","unstructured":"Galbiati, G., Maffioli, F., Morzenti, A.: A short note on the approximability of the maximum leaves spanning tree problem. Inf. Process. Lett. 52(1), 45\u201349 (1994)","journal-title":"Inf. Process. Lett."},{"issue":"3","key":"685_CR16","doi-asserted-by":"crossref","first-page":"113","DOI":"10.1016\/S0020-0190(00)00092-2","volume":"75","author":"D Guan","year":"2000","unstructured":"Guan, D., Chou, C.Y., Chen, C.W.: Computational complexity of similarity retrieval in a pictorial database. Inf. Process. Lett. 75(3), 113\u2013117 (2000)","journal-title":"Inf. Process. Lett."},{"issue":"6","key":"685_CR17","doi-asserted-by":"crossref","first-page":"341","DOI":"10.1145\/360825.360861","volume":"18","author":"DS Hirschberg","year":"1975","unstructured":"Hirschberg, D.S.: A linear space algorithm for computing maximal common subsequences. Commun. ACM 18(6), 341\u2013343 (1975)","journal-title":"Commun. ACM"},{"issue":"5","key":"685_CR18","doi-asserted-by":"crossref","first-page":"188","DOI":"10.1016\/j.ipl.2007.08.028","volume":"105","author":"KS Huang","year":"2008","unstructured":"Huang, K.S., Yang, C.B., Tseng, K.T., Ann, H.Y., Peng, Y.H.: Efficient algorithms for finding interleaving relationship between sequences. Inf. Process. Lett. 105(5), 188\u2013193 (2008)","journal-title":"Inf. Process. Lett."},{"issue":"2\u20133","key":"685_CR19","doi-asserted-by":"crossref","first-page":"99","DOI":"10.1016\/j.ipl.2006.11.006","volume":"102","author":"KS Huang","year":"2007","unstructured":"Huang, K.S., Yang, C.B., Tseng, K.T., Peng, Y.H., Ann, H.Y.: Dynamic programming algorithms for the mosaic longest common subsequence problem. Inf. Process. Lett. 102(2\u20133), 99\u2013103 (2007)","journal-title":"Inf. Process. Lett."},{"issue":"5","key":"685_CR20","doi-asserted-by":"crossref","first-page":"350","DOI":"10.1145\/359581.359603","volume":"20","author":"JW Hunt","year":"1977","unstructured":"Hunt, J.W., Szymanski, T.G.: A fast algorithm for computing longest common subsequences. Commun. ACM 20(5), 350\u2013353 (1977)","journal-title":"Commun. ACM"},{"issue":"2\u20133","key":"685_CR21","doi-asserted-by":"crossref","first-page":"255","DOI":"10.1016\/j.tcs.2008.01.009","volume":"395","author":"CS Iliopoulos","year":"2008","unstructured":"Iliopoulos, C.S., Rahman, M.S.: Algorithms for computing variants of the longest common subsequence problem. Theor. Comput. Sci. 395(2\u20133), 255\u2013267 (2008)","journal-title":"Theor. Comput. Sci."},{"key":"685_CR22","doi-asserted-by":"crossref","first-page":"5","DOI":"10.1007\/BFb0053011","volume-title":"Lectures on Proof Verification and Approximation Algorithms","author":"T Jansen","year":"1998","unstructured":"Jansen, T.: Introduction to the theory of complexity and approximation algorithms. In: Mayr, E.W., Pr\u00f6mel, H.J., Steger, A. (eds.) Lectures on Proof Verification and Approximation Algorithms, pp. 5\u201328. Springer, Berlin (1998)"},{"issue":"1","key":"685_CR23","doi-asserted-by":"crossref","first-page":"27","DOI":"10.1016\/0020-0190(91)90246-E","volume":"37","author":"V Kann","year":"1991","unstructured":"Kann, V.: Maximum bounded 3-dimensional matching is MAX SNP-complete. Inf. Process. Lett. 37(1), 27\u201335 (1991)","journal-title":"Inf. Process. Lett."},{"key":"685_CR24","doi-asserted-by":"crossref","unstructured":"Karp, R.M.: Reducibility among combinatorial problems. In: Proceedings of a Symposium on the Complexity of Computer Computations, pp. 85\u2013103. IBM Thomas J. Watson Research Center, Yorktown Heights, New York (1972)","DOI":"10.1007\/978-1-4684-2001-2_9"},{"issue":"2","key":"685_CR25","doi-asserted-by":"crossref","first-page":"323","DOI":"10.1137\/0206024","volume":"6","author":"DE Knuth","year":"1977","unstructured":"Knuth, D.E., Morris Jr., J.H., Pratt, V.R.: Fast pattern matching in strings. SIAM J. Comput. 6(2), 323\u2013350 (1977)","journal-title":"SIAM J. Comput."},{"issue":"3","key":"685_CR26","doi-asserted-by":"crossref","first-page":"169","DOI":"10.1016\/0020-0255(87)90037-5","volume":"43","author":"K Krithivasan","year":"1987","unstructured":"Krithivasan, K., Sitalakshmi, R.: Efficient two-dimensional pattern matching in the presence of errors. Inf. Sci. 43(3), 169\u2013184 (1987)","journal-title":"Inf. Sci."},{"issue":"10","key":"685_CR27","doi-asserted-by":"crossref","first-page":"1077","DOI":"10.1016\/0031-3203(90)90004-5","volume":"23","author":"SY Lee","year":"1990","unstructured":"Lee, S.Y., Hsu, F.J.: 2D C-string: a new spatial knowledge representation for image database systems. Pattern Recognit. 23(10), 1077\u20131087 (1990)","journal-title":"Pattern Recognit."},{"issue":"3","key":"685_CR28","doi-asserted-by":"crossref","first-page":"305","DOI":"10.1016\/0031-3203(92)90112-V","volume":"25","author":"SY Lee","year":"1992","unstructured":"Lee, S.Y., Hsu, F.J.: Spatial reasoning and similarity retrieval of images using 2D C-string knowledge representation. Pattern Recognit. 25(3), 305\u2013318 (1992)","journal-title":"Pattern Recognit."},{"issue":"6","key":"685_CR29","doi-asserted-by":"crossref","first-page":"675","DOI":"10.1016\/0031-3203(89)90004-6","volume":"22","author":"SY Lee","year":"1989","unstructured":"Lee, S.Y., Shan, M.K., Yang, W.P.: Similarity retrieval of iconic image database. Pattern Recognit. 22(6), 675\u2013682 (1989)","journal-title":"Pattern Recognit."},{"issue":"3","key":"685_CR30","doi-asserted-by":"crossref","first-page":"425","DOI":"10.1016\/0022-0000(91)90023-X","volume":"43","author":"CH Papadimitriou","year":"1991","unstructured":"Papadimitriou, C.H., Yannakakis, M.: Optimization, approximation, and complexity classes. J. Comput. Syst. Sci. 43(3), 425\u2013440 (1991)","journal-title":"J. Comput. Syst. Sci."},{"issue":"4","key":"685_CR31","doi-asserted-by":"crossref","first-page":"334","DOI":"10.14778\/2095686.2095692","volume":"5","author":"M Pawlik","year":"2011","unstructured":"Pawlik, M., Augsten, N.: RTED: a robust algorithm for the tree edit distance. Proc. VLDB Endow. 5(4), 334\u2013345 (2011)","journal-title":"Proc. VLDB Endow."},{"issue":"4","key":"685_CR32","first-page":"1935","volume":"6","author":"YH Peng","year":"2010","unstructured":"Peng, Y.H., Yang, C.B., Huang, K.S., Tseng, C.T., Hor, C.Y.: Efficient sparse dynamic programming for the merged lcs problem with block constraints. Int. J. Innov. Comput. Inf. Control 6(4), 1935\u20131947 (2010)","journal-title":"Int. J. Innov. Comput. Inf. Control"},{"key":"685_CR33","doi-asserted-by":"crossref","unstructured":"Schaefer, T.J.: The complexity of satisfiability problems. In: Proceedings of the 10th Annual ACM Symposium on Theory of Computing, pp. 216\u2013226. ACM (1978)","DOI":"10.1145\/800133.804350"},{"issue":"1","key":"685_CR34","doi-asserted-by":"crossref","first-page":"29","DOI":"10.1016\/0031-3203(84)90033-5","volume":"17","author":"H Tamura","year":"1984","unstructured":"Tamura, H., Yokoya, N.: Image database systems: a survey. Pattern Recognit. 17(1), 29\u201343 (1984)","journal-title":"Pattern Recognit."},{"key":"685_CR35","unstructured":"Tanimoto, S.L.: An iconic\/symbolic data structuring scheme. In: Pattern Recognition and Artificial Intelligence, pp. 452\u2013471 (1976)"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-020-00685-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-020-00685-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-020-00685-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,2,13]],"date-time":"2021-02-13T23:59:20Z","timestamp":1613260760000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-020-00685-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,2,14]]},"references-count":35,"journal-issue":{"issue":"7","published-print":{"date-parts":[[2020,7]]}},"alternative-id":["685"],"URL":"https:\/\/doi.org\/10.1007\/s00453-020-00685-8","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2020,2,14]]},"assertion":[{"value":"26 June 2017","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"27 January 2020","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"14 February 2020","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}