Paper Info
Title
An algorithm for Constrained LCS
Abstract
The problem of finding the Constrained Longest Common Subsequence (CLCS) for three sequences is a problem with many applications. In this paper a novel algorithm to compute the CLCS is proposed. The most important features of the proposed algorithm are: i) This algorithm is able to find a set of possible CLCS solutions instead of simply returning the length of the CLCS. ii) The algorithm is based on the concept regarding dominances between subsequences. iii) It is expected that the time complexity of our proposed algorithm will be O(ℓ|Δ∥D|), where |Δ| is the number of matches between the two longer input sequences, |D| is the size of the resulting sets after applying a dominance concept, and l is the length of the computed LCS. iv) The expected space complexity of our proposed algorithm is O(|Δ| + |D|). v) This algorithm is capable of determining the problem's reliability at a very early stage of its running.
Year
DOI
Venue
2010
10.1109/AICCSA.2010.5586937
AICCSA
Keywords
Field
DocType
dominance concept,computed lcs,constrained lcs,constrained longest common subsequence,important feature,expected space complexity,possible clcs solution,early stage,novel algorithm,proposed algorithm,time complexity,computation theory,computational modeling,longest common subsequence,sequences,space complexity,computational complexity,approximation algorithms,computability theory,string matching,algorithm design and analysis,algorithms
String searching algorithm,Approximation algorithm,Algorithm design,Longest common subsequence problem,Computer science,Algorithm,Time complexity,Theory of computation,Computational complexity theory
Conference
Citations 
PageRank 
References 
0
0.34
3
Authors
4
Name
Order
Citations
PageRank
David Becerra141.43
Wilson Soto201.69
Luis F. Niño3292.61
Yoan J. Pinzon415816.81