期刊
JOURNAL OF COMBINATORIAL OPTIMIZATION
卷 35, 期 2, 页码 331-340出版社
SPRINGER
DOI: 10.1007/s10878-017-0170-9
关键词
Longest increasing subsequence; Common positions; Algorithms; Dual relationship; Longest common increasing subsequence
资金
- National Natural Science Foundation of China [71371129]
Based on the well-known longest increasing subsequence problem and longest common increasing subsequence (LCIS) problem, we propose the longest commonly positioned increasing subsequences (LCPIS) problem. Let and be two input sequences. Let be a subsequence of A and be a subsequence of B such that , and and () are commonly positioned (have the same index ) in A and B respectively but these two elements do not need to be equal. The LCPIS problem aims at finding a pair of subsequences Asub and as long as possible. When all the elements of the two input sequences are positive integers, this paper presents an algorithm with time to compute the LCPIS, where . And we also show a dual relationship between the LCPIS problem and the LCIS problem.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据