Title page for etd-0031116-004017


[Back to Results | New Search]

URN etd-0031116-004017
Author Huang-Ting Chan
Author's Email Address No Public.
Statistics This thesis had been viewed 5351 times. Download 330 times.
Department Computer Science and Engineering
Year 2015
Semester 1
Degree Master
Type of Document
Language English
Title The Definitions and Computation of the Two Dimensional Largest Common Substructure Problems
Date of Defense 2016-01-26
Page Count 98
Keyword
  • Longest Common Subsequence
  • Similarity
  • NP-hard
  • Matrices
  • Integer Linear Programming
  • Heuristic Algorithm
  • Abstract The traditional longest common subsequence (LCS) problem is to find the maximum number of ordered matches in two sequences. The similarity of two one-dimensional sequences can be measured by the LCS algorithms, which have been extensively studied. However, for the two-dimensional data, computing the similarity with an LCS-like approach remains worthy of investigation. In this thesis, we give the more generalized definition of the two-dimensional largest common substructure (TLCS) problem by referring to the traditional LCS concept. With different matching rules, we thus define four versions of TLCS problems. We also show that two of the TLCS problems are NP-hard by another proof way. Then, we develop some methods for solving the TLCS problem. We first provide two integer linear programming formulas to solve the TLCS problem. Furthermore, we devise two heuristic algorithms for finding a sub-optimal solution efficiently.
    Advisory Committee
  • Tzung-Pei Hong - chair
  • Hsing-Yen Ann - co-chair
  • D. J. Guan - co-chair
  • Chang-Biau Yang - advisor
  • Files
  • etd-0031116-004017.pdf
  • Indicate in-campus at 0 year and off-campus access at 1 year.
    Date of Submission 2016-01-31

    [Back to Results | New Search]


    Browse | Search All Available ETDs

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