Heikki Hyyrö

A hardness result and new algorithm for the longest common palindromic subsequence problem

2016 · arXiv (Cornell University)

The 2-LCPS problem, first introduced by Chowdhury et al. [Fundam. Inform., 129(4):329-340, 2014], asks one to compute (the length of) a longest palindromic common subsequence between two given strings $A$ and $B$. We show that …