{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,26]],"date-time":"2025-03-26T10:32:15Z","timestamp":1742985135100,"version":"3.40.3"},"publisher-location":"Singapore","reference-count":17,"publisher":"Springer Nature Singapore","isbn-type":[{"type":"print","value":"9789811934438"},{"type":"electronic","value":"9789811934445"}],"license":[{"start":{"date-parts":[[2022,1,1]],"date-time":"2022-01-01T00:00:00Z","timestamp":1640995200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2022,1,1]],"date-time":"2022-01-01T00:00:00Z","timestamp":1640995200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2022]]},"DOI":"10.1007\/978-981-19-3444-5_7","type":"book-chapter","created":{"date-parts":[[2022,7,26]],"date-time":"2022-07-26T09:05:06Z","timestamp":1658826306000},"page":"77-86","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Sequence Classification via\u00a0LCS"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-6124-2965","authenticated-orcid":false,"given":"Riccardo","family":"Dondi","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2022,7,27]]},"reference":[{"key":"7_CR1","doi-asserted-by":"crossref","unstructured":"Abboud, A., Backurs, A., Williams, V.V.: Tight hardness results for LCS and other sequence similarity measures. In: Guruswami, V. (ed.) IEEE 56th Annual Symposium on Foundations of Computer Science, FOCS 2015, Berkeley, CA, USA, 17\u201320 Oct 2015, pp. 59\u201378. IEEE Computer Society (2015)","DOI":"10.1109\/FOCS.2015.14"},{"key":"7_CR2","unstructured":"Abboud, A., Rubinstein, A.: Fast and deterministic constant factor approximation algorithms for LCS imply new circuit lower bounds. In: Karlin, A.R. (ed.) 9th Innovations in Theoretical Computer Science Conference, ITCS 2018, 11\u201314 Jan 2018, Cambridge, MA, USA. LIPIcs, vol.\u00a094, pp. 35:1\u201335:14. Schloss Dagstuhl\u2014Leibniz-Zentrum f\u00fcr Informatik (2018)"},{"issue":"7","key":"7_CR3","doi-asserted-by":"publisher","first-page":"272","DOI":"10.1016\/j.ipl.2011.12.009","volume":"112","author":"G Blin","year":"2012","unstructured":"Blin, G., Bonizzoni, P., Dondi, R., Sikora, F.: On the parameterized complexity of the repetition free longest common subsequence problem. Inf. Process. Lett. 112(7), 272\u2013276 (2012)","journal-title":"Inf. Process. Lett."},{"key":"7_CR4","doi-asserted-by":"publisher","DOI":"10.1016\/j.cor.2020.105089","volume":"125","author":"C Blum","year":"2021","unstructured":"Blum, C., Djukanovic, M., Santini, A., Jiang, H., Li, C., Many\u00e0, F., Raidl, G.R.: Solving longest common subsequence problems via a transformation to the maximum clique problem. Comput. Oper. Res. 125, 105089 (2021)","journal-title":"Comput. Oper. Res."},{"key":"7_CR5","doi-asserted-by":"crossref","unstructured":"Boroujeni, M., Seddighin, M., Seddighin, S.: Improved algorithms for edit distance and LCS: beyond worst case. In: Chawla, S. (ed.) Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, SODA 2020, Salt Lake City, UT, USA, 5\u20138 Jan 2020, pp. 1601\u20131620. SIAM (2020)","DOI":"10.1137\/1.9781611975994.99"},{"key":"7_CR6","unstructured":"Bringmann, K., Das, D.: A linear-time n$${}^{\\text{0.4}}$$-approximation for longest common subsequence. In: Bansal, N., Merelli, E., Worrell, J. (eds.) 48th International Colloquium on Automata, Languages, and Programming, ICALP 2021, 12\u201316 July 2021, Glasgow, Scotland (Virtual Conference). LIPIcs, vol.\u00a0198, pp. 39:1\u201339:20. Schloss Dagstuhl\u2014Leibniz-Zentrum f\u00fcr Informatik (2021)"},{"key":"7_CR7","doi-asserted-by":"publisher","first-page":"272","DOI":"10.1016\/j.tcs.2019.09.022","volume":"796","author":"M Castelli","year":"2019","unstructured":"Castelli, M., Dondi, R., Mauri, G., Zoppis, I.: Comparing incomplete sequences via longest common subsequence. Theor. Comput. Sci. 796, 272\u2013285 (2019)","journal-title":"Theor. Comput. Sci."},{"key":"7_CR8","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2020.106041","volume":"166","author":"M Djukanovic","year":"2021","unstructured":"Djukanovic, M., Berger, C., Raidl, G.R., Blum, C.: An a* search algorithm for the constrained longest common subsequence problem. Inf. Process. Lett. 166, 106041 (2021)","journal-title":"Inf. Process. Lett."},{"issue":"3","key":"7_CR9","doi-asserted-by":"publisher","first-page":"871","DOI":"10.1109\/TSMCB.2012.2217324","volume":"43","author":"D Frolova","year":"2013","unstructured":"Frolova, D., Stern, H., Berman, S.: Most probable longest common subsequence for recognition of gesture character input. IEEE Trans. Cybern. 43(3), 871\u2013880 (2013)","journal-title":"IEEE Trans. Cybern."},{"key":"7_CR10","doi-asserted-by":"crossref","unstructured":"Hinkemeyer, B., Julstrom, B.A.: A genetic algorithm for the longest common subsequence problem. In: Cattolico, M. (ed.) Genetic and Evolutionary Computation Conference, GECCO 2006, Proceedings, Seattle, Washington, USA, 8\u201312 July 2006, pp. 609\u2013610. ACM (2006)","DOI":"10.1145\/1143997.1144105"},{"issue":"6","key":"7_CR11","doi-asserted-by":"publisher","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"},{"key":"7_CR12","doi-asserted-by":"crossref","unstructured":"Hsiao, K., Xu, K.S., Calder, J., III, A.O.H.: Multicriteria similarity-based anomaly detection using Pareto depth analysis. IEEE Trans. Neural Netw. Learn. Syst. 27(6), 1307\u20131321 (2016)","DOI":"10.1109\/TNNLS.2015.2466686"},{"issue":"2\u20133","key":"7_CR13","doi-asserted-by":"publisher","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."},{"issue":"1","key":"7_CR14","doi-asserted-by":"publisher","first-page":"170","DOI":"10.1007\/s00453-008-9243-6","volume":"57","author":"T Jansen","year":"2010","unstructured":"Jansen, T., Weyland, D.: Analysis of evolutionary algorithms for the longest common subsequence problem. Algorithmica 57(1), 170\u2013186 (2010)","journal-title":"Algorithmica"},{"issue":"5","key":"7_CR15","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. 24(5), 1122\u20131139 (1995)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"7_CR16","doi-asserted-by":"publisher","first-page":"166","DOI":"10.3390\/s19010166","volume":"19","author":"R Khan","year":"2019","unstructured":"Khan, R., Ali, I., Altowaijri, S.M., Zakarya, M., Rahman, A.U., Ahmedy, I., Khan, A., Gani, A.: LCSS-based algorithm for computing multivariate data set similarity: a case study of real-time WSN data. Sensors 19(1), 166 (2019)","journal-title":"Sensors"},{"issue":"8","key":"7_CR17","doi-asserted-by":"publisher","first-page":"2444","DOI":"10.1073\/pnas.85.8.2444","volume":"85","author":"WR Pearson","year":"1988","unstructured":"Pearson, W.R., Lipman, D.J.: Improved tools for biological sequence comparison. Proc. Natl. Acad. Sci. U. S. A. 85(8), 2444\u20132448 (1988)","journal-title":"Proc. Natl. Acad. Sci. U. S. A."}],"container-title":["Smart Innovation, Systems and Technologies","Intelligent Decision Technologies"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-981-19-3444-5_7","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,7,26]],"date-time":"2022-07-26T09:10:49Z","timestamp":1658826649000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-981-19-3444-5_7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022]]},"ISBN":["9789811934438","9789811934445"],"references-count":17,"URL":"https:\/\/doi.org\/10.1007\/978-981-19-3444-5_7","relation":{},"ISSN":["2190-3018","2190-3026"],"issn-type":[{"type":"print","value":"2190-3018"},{"type":"electronic","value":"2190-3026"}],"subject":[],"published":{"date-parts":[[2022]]},"assertion":[{"value":"27 July 2022","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}