A Survey of the Longest Common Subsequence Problem and Its Related Problems

by Chen, Jian-bein

Abstract (Summary)
ABSTRACT The longest common subsequence (LCS) problem is a classical problem both in com- binational optimization and computational biology. During the past few decades, a considerable number of studies have been focused on LCS and its related prob- lems. In this thesis, we shall present a complete survey on LCS and its related problems, and review some e¡Ócient algorithms for solving these problems. We shall also give the de¡Ânition to each problem, present some theorems, and illustrate time complexity and space complexity of the algorithms for solving these problems.
Bibliographical Information:

Advisor:Chang-biau Yang; none; Yue-li Wang; Chia-ning Yang; Wu-chih Hu

School:National Sun Yat-Sen University

School Location:China - Taiwan

Source Type:Master's Thesis

Keywords:lcs longest common subsequence


Date of Publication:09/12/2005

© 2009 All Rights Reserved.