| アイテムタイプ |
学術雑誌論文 = Journal Article(1) |
| 公開日 |
2023-07-31 |
| 資源タイプ |
|
|
資源タイプ識別子 |
http://purl.org/coar/resource_type/c_6501 |
|
資源タイプ |
journal article |
| タイトル |
|
|
タイトル |
Exact Algorithms for the Bounded Repetition Longest Common Subsequence Problem |
|
言語 |
en |
| 言語 |
|
|
言語 |
eng |
| 著者 |
Asahiro, Yuichi
Jansson, Jesper
Lin, Guohui
宮野, 英次
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 r-REPETITION LONGEST COMMON SUBSEQUENCE problem (or r-RLCS, for short): Given two sequences X and Y over an alphabet S, find a longest common subsequence of X and Y such that each symbol appears at most r times in the obtained subsequence. Without loss of generality, we will assume that |X|≤|Y|| from here on. The special case of 1-RLCS, also known as the REPETITION-FREE LONGEST COMMON SUBSEQUENCE problem (RFLCS), has been studied previously; e.g., in [1], Adi et al. presented an (exponential-time) integer linear programming-based exact algorithm for 1-RLCS. However, they did not analyze its time complexity, and to the best of our knowledge, there are no previous results on the running times of any exact algorithms for this problem. In this paper, we first propose a simple algorithm for 1-RLCS based on the strategy used in [1] and show explicitly that its running time is bounded by O(1.44225|X||X||Y|). Next, we provide a DP-based algorithm for r-RLCS and prove that its running time is O((r+1)|X|/(r+1)|X||Y|) for any r≥1. In particular, our new algorithm runs in O(1.41422|X||X||Y|) time for 1-RLCS, which is faster than the previous one. |
|
言語 |
en |
| 備考 |
|
|
内容記述タイプ |
Other |
|
内容記述 |
13th International Conference on Combinatorial Optimization and Applications, COCOA 2019, December 13–15, 2019, Xiamen, China |
|
言語 |
en |
| 書誌情報 |
en : Lecture Notes in Computer Science
巻 11949,
p. 1-12,
発行日 2019-11-23
|
| 出版社 |
|
|
出版者 |
Springer |
| DOI |
|
|
|
識別子タイプ |
DOI |
|
|
関連識別子 |
https://doi.org/10.1007/978-3-030-36412-0_1 |
| ISBN |
|
|
|
識別子タイプ |
ISBN |
|
|
関連識別子 |
978-3-030-36411-3 |
| ISBN |
|
|
|
識別子タイプ |
ISBN |
|
|
関連識別子 |
978-3-030-36412-0 |
| ISSN |
|
|
収録物識別子タイプ |
EISSN |
|
収録物識別子 |
1611-3349 |
| ISSN |
|
|
収録物識別子タイプ |
PISSN |
|
収録物識別子 |
0302-9743 |
| 著作権関連情報 |
|
|
権利情報 |
Copyright (c) 2019 Springer Nature Switzerland AG. This is a post-peer-review, pre-copyedit version of an article published in Lecture Notes in Computer Science. The final authenticated version is available online at: https://doi.org/10.1007/978-3-030-36412-0_1. |
| 出版タイプ |
|
|
出版タイプ |
AM |
|
出版タイプResource |
http://purl.org/coar/version/c_ab4af688f83e57aa |
| 査読の有無 |
|
|
値 |
yes |
| 研究者情報 |
|
|
URL |
https://hyokadb02.jimu.kyutech.ac.jp/html/233_ja.html |
978-3-030-36412-0_1.pdf (364 KB)
