| URN |
etd-0031116-004017 |
|---|
| Author |
Huang-Ting Chan |
|---|
| Author's Email Address |
No Public. |
|---|
| Statistics |
This thesis had been viewed 5577 times. Download 373 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 |
Indicate in-campus at 0 year and off-campus access at 1 year. |
|---|
| Date of Submission |
2016-01-31 |
|---|
