WEKO3
アイテム
Exact algorithms for the repetition-bounded longest common subsequence problem
http://hdl.handle.net/10228/00008953
http://hdl.handle.net/10228/000089538474c752-0034-4e99-8b1c-d981a394120f
| 名前 / ファイル | ライセンス | アクション |
|---|---|---|
10358995.pdf (224.1 kB)
|
|
| アイテムタイプ | 学術雑誌論文 = Journal Article(1) | |||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 公開日 | 2022-08-04 | |||||||||||||
| 資源タイプ | ||||||||||||||
| 資源タイプ識別子 | http://purl.org/coar/resource_type/c_6501 | |||||||||||||
| 資源タイプ | journal article | |||||||||||||
| タイトル | ||||||||||||||
| タイトル | Exact algorithms for the repetition-bounded longest common subsequence problem | |||||||||||||
| 言語 | en | |||||||||||||
| 言語 | ||||||||||||||
| 言語 | eng | |||||||||||||
| 著者 |
Asahiro, Yuichi
× Asahiro, Yuichi× Jansson, Jesper× Lin, Guohui× 宮野, 英次
WEKO
6037
× Ono, Hirotaka× Utashima, Tadatoshi |
|||||||||||||
| 抄録 | ||||||||||||||
| 内容記述タイプ | Abstract | |||||||||||||
| 内容記述 | In this paper, we study exact, exponential-time algorithms for a variant of the classic Longest Common Subsequence problem called the Repetition-Bounded Longest Common Subsequence problem (or RBLCS, for short): Let an alphabet S be a finite set of symbols and an occurrence constraint Cocc be a function Cocc: S → N, assigning an upper bound on the number of occurrences of each symbol in S. Given two sequences X and Y over the alphabet S and an occurrence constraint Cocc, the goal of RBLCS is to find a longest common subsequence of X and Y such that each symbol s ∈ S appears at most Cocc(s) times in the obtained subsequence. The special case where Cocc(s) = 1 for every symbol s ∈ S is known as the Repetition-Free Longest Common Subsequence problem (RFLCS) and has been studied previously; e.g., in [1], Adi et al. presented a simple (exponential-time) exact algorithm for RFLCS. However, they did not analyze its time complexity in detail, and to the best of our knowledge, there are no previous results on the running times of any exact algorithms for this problem. Without loss of generality, we will assume that |X| ≤ |Y | and |X| = n. In this paper, we first propose a simpler algorithm for RFLCS based on the strategy used in [1] and show explicitly that its running time is O(1.44225n). Next, we provide a dynamic programming (DP) based algorithm for RBLCS and prove that its running time is O(1.44225n) for any occurrence constraint Cocc, and even less in certain special cases. In particular, for RFLCS, our DP-based algorithm runs in O(1.41422n) time, which is faster than the previous one. Furthermore, we prove NP-hardness and APX-hardness results for RBLCS on restricted instances. | |||||||||||||
| 言語 | en | |||||||||||||
| 書誌情報 |
en : Theoretical Computer Science 巻 838, p. 238-249, 発行日 2020-08-04 |
|||||||||||||
| 出版社 | ||||||||||||||
| 出版者 | Elsevier | |||||||||||||
| DOI | ||||||||||||||
| 関連タイプ | isVersionOf | |||||||||||||
| 識別子タイプ | DOI | |||||||||||||
| 関連識別子 | https://doi.org/10.1016/j.tcs.2020.07.042 | |||||||||||||
| 日本十進分類法 | ||||||||||||||
| 主題Scheme | NDC | |||||||||||||
| 主題 | 548 | |||||||||||||
| NCID | ||||||||||||||
| 収録物識別子タイプ | NCID | |||||||||||||
| 収録物識別子 | AA00862688 | |||||||||||||
| ISSN | ||||||||||||||
| 収録物識別子タイプ | PISSN | |||||||||||||
| 収録物識別子 | 0304-3975 | |||||||||||||
| ISSN | ||||||||||||||
| 収録物識別子タイプ | EISSN | |||||||||||||
| 収録物識別子 | 1879-2294 | |||||||||||||
| 著作権関連情報 | ||||||||||||||
| 権利情報 | Copyright (c) 2020 Elsevier B.V. All rights reserved. | |||||||||||||
| キーワード | ||||||||||||||
| 主題Scheme | Other | |||||||||||||
| 主題 | Repetition-bounded longest common subsequence problem | |||||||||||||
| キーワード | ||||||||||||||
| 主題Scheme | Other | |||||||||||||
| 主題 | Repetition-free | |||||||||||||
| キーワード | ||||||||||||||
| 主題Scheme | Other | |||||||||||||
| 主題 | Exponential-time exact algorithms | |||||||||||||
| キーワード | ||||||||||||||
| 主題Scheme | Other | |||||||||||||
| 主題 | Dynamic programming | |||||||||||||
| キーワード | ||||||||||||||
| 主題Scheme | Other | |||||||||||||
| 主題 | NP-hardness | |||||||||||||
| キーワード | ||||||||||||||
| 主題Scheme | Other | |||||||||||||
| 主題 | APX-hardness | |||||||||||||
| 出版タイプ | ||||||||||||||
| 出版タイプ | AM | |||||||||||||
| 出版タイプResource | http://purl.org/coar/version/c_ab4af688f83e57aa | |||||||||||||
| 査読の有無 | ||||||||||||||
| 値 | yes | |||||||||||||
| 研究者情報 | ||||||||||||||
| URL | https://hyokadb02.jimu.kyutech.ac.jp/html/233_ja.html | |||||||||||||
| 論文ID（連携） | ||||||||||||||
| 値 | 10358995 | |||||||||||||
| 連携ID | ||||||||||||||
| 値 | 8410 | |||||||||||||
