Semi-local longest common subsequences and maximum cliques in circle graphs

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