Semi-local longest common subsequences and maximum cliques in circle graphs
Alexander Tiskin · 2006
For two strings a, b of lengths m, n respectively, the longest common subsequence (LCS) problem consists in comparing a and b by computing the length of their LCS. In a previous paper, we defined a generalisation, called “the all semi-local LCS problem”, for which we proposed an ecient geometric output representation, and an ecient algorithm running in time o(mn) when m and n are reasonably close. In this paper, we consider a restriction of the all semi-local LCS problem to strings that are permutations of a given set of size n. The resulting problem is equivalent to finding all local longest increasing subsequences (LIS) in a permutation. We propose an algorithm for this problem running in time O(n 1.5 ). As an interesting application of our method, we propose a new algorithm for finding a maximum clique in a circle graph on n nodes, also running in time O(n 1.5 ). Compared to a number of previous algorithms for these problems, our approach presents a substantial improvement in worst-case running time.