Paper Info
Title
Bit-Parallel Branch and Bound Algorithm for Transposition Invariant LCS
Abstract
We consider the problem of longest common subsequence (LCS) of two given strings in the case where the first may be shifted by some constant (i.e. transposed) to match the second. For this longest common transposition invariant subsequence (LCTS) problem, that has applications for instance in music comparison, we develop a branch and bound algorithm with best case time O((m 2 + loglog σ) logσ) and worst case time O((m 2 + log σ) σ), where m and σ are the length of the strings and the number of possible transpositions, respectively. This compares favorably against the O(σm 2) naive algorithm in most cases and, for large m, against the O(m 2loglog m) time algorithm of [2].
Year
DOI
Venue
2004
10.1007/978-3-540-30213-1_10
Lecture Notes in Computer Science
Keywords
Field
DocType
branch and bound algorithm,longest common subsequence
Discrete mathematics,Transposition (music),Combinatorics,Branch and bound,Longest common subsequence problem,Parallel algorithm,Priority queue,Invariant (mathematics),Subsequence,String (computer science),Mathematics
Conference
Volume
ISSN
Citations 
3246
0302-9743
2
PageRank 
References 
Authors
0.42
3
3
Name
Order
Citations
PageRank
Kjell Lemström119022.55
Gonzalo Navarro26088345.16
Yoan J. Pinzon315816.81