0000000000948959

AUTHOR

Brenda S. Baker

showing 2 related works from this author

Longest Common Subsequence from Fragments via Sparse Dynamic Programming

1998

Sparse Dynamic Programming has emerged as an essential tool for the design of efficient algorithms for optimization problems coming from such diverse areas as Computer Science, Computational Biology and Speech Recognition [7,11,15]. We provide a new Sparse Dynamic Programming technique that extends the Hunt-Szymanski [2,9,8] paradigm for the computation of the Longest Common Subsequence (LCS) and apply it to solve the LCS from Fragments problem: given a pair of strings X and Y (of length n and m, resp.) and a set M of matching substrings of X and Y, find the longest common subsequence based only on the symbol correspondences induced by the substrings. This problem arises in an application t…

Dynamic programmingCombinatoricsSet (abstract data type)Longest common subsequence problemOptimization problemMatching (graph theory)Combinatorial optimizationData structureSubstringMathematics
researchProduct

Sparse Dynamic Programming for Longest Common Subsequence from Fragments

2002

Sparse Dynamic Programming has emerged as an essential tool for the design of efficient algorithms for optimization problems coming from such diverse areas as computer science, computational biology, and speech recognition. We provide a new sparse dynamic programming technique that extends the Hunt?Szymanski paradigm for the computation of the longest common subsequence (LCS) and apply it to solve the LCS from Fragments problem: given a pair of strings X and Y (of length n and m, respectively) and a set M of matching substrings of X and Y, find the longest common subsequence based only on the symbol correspondences induced by the substrings. This problem arises in an application to analysis…

Longest common subsequence problemCombinatoricsDynamic programmingSet (abstract data type)Computational MathematicsControl and OptimizationOptimization problemComputational Theory and MathematicsMatching (graph theory)Symbol (programming)ComputationSubstringMathematicsJournal of Algorithms
researchProduct