Paper Info
Title
Longest common subsequences in permutations and maximum cliques in circle graphs
Abstract
For two strings a, b, 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 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(n1.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(n1.5). Compared to a number of previous algorithms for this problem, our approach presents a substantial improvement in worst-case running time.
Year
DOI
Venue
2006
10.1007/11780441_25
CPM
Keywords
Field
DocType
circle graph,n node,resulting problem,longest common subsequence,efficient output representation,asymptotic time o,new algorithm,efficient algorithm,semi-local lcs problem,time o,previous algorithm,maximum clique,longest increasing subsequence
Graph theory,Discrete mathematics,Combinatorics,Longest common subsequence problem,Longest increasing subsequence,Circle graph,Clique,Computer science,Permutation,String (computer science),Clique (graph theory)
Conference
Volume
ISSN
ISBN
4009
0302-9743
3-540-35455-7
Citations 
PageRank 
References 
7
0.48
13
Authors
1
Name
Order
Citations
PageRank
Alexander Tiskin122015.50