A diagonal-based algorithm for the longest common increasing subsequence problem
| Autor: | Kuo-Si Huang, Shou-Fu Lo, Chang-Biau Yang, Kuo-Tsung Tseng |
|---|---|
| Rok vydání: | 2020 |
| Předmět: |
General Computer Science
Diagonal 0102 computer and information sciences 02 engineering and technology Function (mathematics) Extension (predicate logic) Data structure 01 natural sciences Theoretical Computer Science Set (abstract data type) 010201 computation theory & mathematics Van Emde Boas tree Subsequence 0202 electrical engineering electronic engineering information engineering 020201 artificial intelligence & image processing Time complexity Algorithm Mathematics |
| Zdroj: | Theoretical Computer Science. 815:69-78 |
| ISSN: | 0304-3975 |
| DOI: | 10.1016/j.tcs.2020.02.024 |
| Popis: | The longest common increasing subsequences (LCIS) problem is to find out a common increasing subsequence with the maximal length of two given sequences A and B. In this paper, we propose an algorithm for solving the LCIS problem with O ( ( n + L ( m − L ) ) log log | Σ | ) time and O(n) space, where m and n denote the lengths of A and B, respectively, m ≤ n , L denotes the LCIS length, and Σ denotes the alphabet set. The main idea of our algorithm is to extend the answer from some previously feasible solutions, in which the domination function is invoked. To accomplish the extension and domination functions, the data structure of the van Emde Boas tree is utilized. From the time complexity, it is obvious that our algorithm is extremely efficient when L is very small or L is close to m. Some experiments are performed to demonstrate the efficiency of our algorithm. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect