Title page for etd-0912112-090312


[Back to Results | New Search]

URN etd-0912112-090312
Author Kai-Yuan Cheng
Author's Email Address chengky@par.cse.nsysu.edu.tw
Statistics This thesis had been viewed 5351 times. Download 561 times.
Department Computer Science and Engineering
Year 2012
Semester 1
Degree Master
Type of Document
Language English
Title The Longest Common Subsequence Problem with a Gapped Constraint
Date of Defense 2012-09-07
Page Count 49
Keyword
  • DP
  • Dynamic Programming
  • constraint
  • CLCS
  • LCS
  • Gap
  • Abstract This thesis considers a variant of the classical problem for finding the longest common subsequence (LCS) called longest common subsequence problem with a gapped constraint (LCSGC). Given two sequences A, B, and a constrained sequence C, which is accomplished with a corresponding gapped constraint for each symbol, whose lengths are m, n, and r, respectively, the LCSGC problem is to find an LCS of A and B, such that C is also a subsequence of this LCS and the gapped constraints corresponding to C are satisfied. In this thesis, two algorithms with time complexities O(m2n2r) and O(mnr × min(m, n)) are proposed based on the dynamic programming technique for solving the LCSGC problem.
    Advisory Committee
  • Chung-Nan Lee - chair
  • Hsing-Yen Ann - co-chair
  • Yung-Hsing Peng - co-chair
  • Kuo-Si Huang - co-chair
  • Chang-Biau Yang - advisor
  • Files
  • etd-0912112-090312.pdf
  • Indicate in-campus at 0 year and off-campus access at 1 year.
    Date of Submission 2012-09-12

    [Back to Results | New Search]


    Browse | Search All Available ETDs

    If you have more questions or technical problems, please contact eThesys