Sequence Classification via LCS

1. 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–20 Oct 2015, pp. 59–78. IEEE Computer Society (2015)

   Google Scholar 

2. 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–14 Jan 2018, Cambridge, MA, USA. LIPIcs, vol. 94, pp. 35:1–35:14. Schloss Dagstuhl—Leibniz-Zentrum für Informatik (2018)

   Google Scholar 

3. 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–276 (2012)

   Article  MathSciNet  Google Scholar 

4. Blum, C., Djukanovic, M., Santini, A., Jiang, H., Li, C., Manyà, F., Raidl, G.R.: Solving longest common subsequence problems via a transformation to the maximum clique problem. Comput. Oper. Res. 125, 105089 (2021)

   Article  MathSciNet  Google Scholar 

5. 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–8 Jan 2020, pp. 1601–1620. SIAM (2020)

   Google Scholar 

6. 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–16 July 2021, Glasgow, Scotland (Virtual Conference). LIPIcs, vol. 198, pp. 39:1–39:20. Schloss Dagstuhl—Leibniz-Zentrum für Informatik (2021)

   Google Scholar 

7. Castelli, M., Dondi, R., Mauri, G., Zoppis, I.: Comparing incomplete sequences via longest common subsequence. Theor. Comput. Sci. 796, 272–285 (2019)

   Article  MathSciNet  Google Scholar 

8. 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)

   Article  MathSciNet  Google Scholar 

9. Frolova, D., Stern, H., Berman, S.: Most probable longest common subsequence for recognition of gesture character input. IEEE Trans. Cybern. 43(3), 871–880 (2013)

   Article  Google Scholar 

10. 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–12 July 2006, pp. 609–610. ACM (2006)

    Google Scholar 

11. Hirschberg, D.S.: A linear space algorithm for computing maximal common subsequences. Commun. ACM 18(6), 341–343 (1975)

    Article  MathSciNet  Google Scholar 

12. 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–1321 (2016)

    Google Scholar 

13. Iliopoulos, C.S., Rahman, M.S.: Algorithms for computing variants of the longest common subsequence problem. Theor. Comput. Sci. 395(2–3), 255–267 (2008)

    Article  MathSciNet  Google Scholar 

14. Jansen, T., Weyland, D.: Analysis of evolutionary algorithms for the longest common subsequence problem. Algorithmica 57(1), 170–186 (2010)

    Article  MathSciNet  Google Scholar 

15. Jiang, T., Li, M.: On the approximation of shortest common supersequences and longest common subsequences. SIAM J. Comput. 24(5), 1122–1139 (1995)

    Article  MathSciNet  Google Scholar 

16. 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)

    Article  Google Scholar 

17. Pearson, W.R., Lipman, D.J.: Improved tools for biological sequence comparison. Proc. Natl. Acad. Sci. U. S. A. 85(8), 2444–2448 (1988)

    Article  Google Scholar 

Download references