Longest Common Subsequences in Permutations and Maximum Cliques in Circle Graphs

摘要

For two strings a, b, the longest common subsequence (LCS) problem consists in comparing a and 6 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 efficient output representation and an efficient algorithm. In this paper, we consider a restriction of this problem to strings that are permutations of a given set. The resulting problem is equivalent to the all local longest increasing subsequences (LIS) problem. We propose an algorithm for this problem, running in time O(n~(1.5)) on an input of size n. As an interesting application of our method, we propose a new algorithm for finding a maximum clique in a circle graph on n nodes, running in the same asymptotic time O(n~(1.5)). Compared to a number of previous algorithms for this problem, our approach presents a substantial improvement in worst-case running time.