Computing the longest common almost-increasing subsequence

被引：2

作者：

Bhuiyan, Mohammad Tawhidul Hasan ^{[1
]}

Alam, Muhammad Rashed ^{[1
]}

Rahman, M. Sohel ^{[1
]}

机构：

[1] BUET, Dept CSE, ECE Bldg, Dhaka 1205, Bangladesh

来源：

THEORETICAL COMPUTER SCIENCE | 2022年 / 930卷

关键词：

Algorithms; Longest common subsequence; Longest increasing subsequence; ALGORITHMS;

D O I：

10.1016/j.tcs.2022.07.021

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

In this paper, we revisit the problem of computing longest common almost increasing subsequence (LCAIS) where, given two input sequences, the goal is to compute a common subsequence that is 'almost' increasing. Here the concept of an almost increasing subsequence offers an interesting relaxation over the increasing condition. This problem has been studied in the literature albeit with some constraints. Here, we present a number of a number of algorithmic approaches to solve the problem more generally and efficiently. (c) 2022 Elsevier B.V. All rights reserved.

引用

页码：157 / 178

页数：22

共 28 条

[1]

Abboud A., 2018, 9 INN THEOR COMP SCI, P35, DOI [10.4230/LIPIcs.ITCS.2018.35, DOI 10.4230/LIPICS.ITCS.2018.35]

[2] Tight Hardness Results for LCS and other Sequence Similarity Measures [J].

Abboud, Amir ;

Backurs, Arturs ;

Williams, Virginia Vassilevska .

2015 IEEE 56TH ANNUAL SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE, 2015, :59-78

[3]

[Anonymous], 1975, 16 ANN S FDN COMP SC, DOI [10.1016/0020-0190(77)90031-X, DOI 10.1109/SFCS.1975.26]

[4]

[Anonymous], 2009, Introduction to Algorithms

[5]

Bringmann K, 2018, SODA'18: PROCEEDINGS OF THE TWENTY-NINTH ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS, P1216

[6] Quadratic Conditional Lower Bounds for String Problems and Dynamic TimeWarping [J].

Bringmann, Karl ;

Kuennemann, Marvin .

2015 IEEE 56TH ANNUAL SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE, 2015, :79-97

[7] On the generalized constrained longest common subsequence problems [J].

Chen, Yi-Ching ;

Chao, Kun-Mao .

JOURNAL OF COMBINATORIAL OPTIMIZATION, 2011, 21 (03) :383-392

[8]

Duraj Lech, 2018, TIGHT CONDITIONAL LO, DOI [10.1007/s00453-018-0485-7, DOI 10.1007/S00453-018-0485-7]

[9]

Elmasry A, 2010, LECT NOTES COMPUT SC, V6196, P338, DOI 10.1007/978-3-642-14031-0_37

[10] COMPUTING LENGTH OF LONGEST INCREASING SUBSEQUENCES [J].

FREDMAN, ML .

DISCRETE MATHEMATICS, 1975, 11 (01) :29-35

← 1 2 3 →