The Library
Longest common subsequences in permutations and maximum cliques in circle graphs
Tools
Tiskin, Alexander (2006) Longest common subsequences in permutations and maximum cliques in circle graphs. In: Lewenstein, M. and Valiente, G., (eds.) Longest Common Subsequences in Permutations and Maximum Cliques in Circle Graphs. Lecture Notes in Computer Science, Volume 4009 . Springer Berlin Heidelberg, pp. 270-281. ISBN 9783540354550
PDF
fulltext10.pdf - Published Version Embargoed item. Restricted access to Repository staff only - Requires a PDF viewer. Download (435Kb) |
Official URL: http://dx.doi.org/10.1007/11780441_25
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(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 appreach presents a substantial improvement in worst-case running time.
Item Type: | Book Item | ||||
---|---|---|---|---|---|
Subjects: | Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software | ||||
Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | ||||
Series Name: | Lecture Notes in Computer Science | ||||
Publisher: | Springer Berlin Heidelberg | ||||
ISBN: | 9783540354550 | ||||
ISSN: | 0302-9743 | ||||
Book Title: | Longest Common Subsequences in Permutations and Maximum Cliques in Circle Graphs | ||||
Editor: | Lewenstein, M. and Valiente, G. | ||||
Official Date: | 2006 | ||||
Dates: |
|
||||
Volume: | Volume 4009 | ||||
Number of Pages: | 12 | ||||
Page Range: | pp. 270-281 | ||||
DOI: | 10.1007/11780441_25 | ||||
Status: | Peer Reviewed | ||||
Publication Status: | Published | ||||
Date of first compliant deposit: | 15 December 2015 | ||||
Title of Event: | 17th Annual Symposium on Combinatorial Pattern Matching | ||||
Location of Event: | Tech Univ Catolonia, Barcelona, Spain | ||||
Date(s) of Event: | 05-07 Jul 2006 |
Data sourced from Thomson Reuters' Web of Knowledge
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |