TY - GEN

T1 - Exact Algorithms for the Bounded Repetition Longest Common Subsequence Problem

AU - Asahiro, Yuichi

AU - Jansson, Jesper Andreas

AU - Lin, Guohui

AU - Miyano, Eiji

AU - Ono, Hirotaka

AU - Utashima, Tadatoshi

PY - 2019/1/1

Y1 - 2019/1/1

N2 - 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 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. Next, we provide a DP-based algorithm for r-RLCS and prove that its running time is for any. In particular, our new algorithm runs in time for 1-RLCS, which is faster than the previous one.

AB - 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 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. Next, we provide a DP-based algorithm for r-RLCS and prove that its running time is for any. In particular, our new algorithm runs in time for 1-RLCS, which is faster than the previous one.

UR - http://www.scopus.com/inward/record.url?scp=85078537609&partnerID=8YFLogxK

U2 - 10.1007/978-3-030-36412-0_1

DO - 10.1007/978-3-030-36412-0_1

M3 - Conference article published in proceeding or book

AN - SCOPUS:85078537609

SN - 9783030364113

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 1

EP - 12

BT - Combinatorial Optimization and Applications - 13th International Conference, COCOA 2019, Proceedings

A2 - Li, Yingshu

A2 - Cardei, Mihaela

A2 - Huang, Yan

PB - Springer

T2 - 13th Annual International Conference on Combinatorial Optimization and Applications, COCOA 2019

Y2 - 13 December 2019 through 15 December 2019

ER -