Fast computation of a longest increasing subsequence and application

TY - JOUR

T1 - Fast computation of a longest increasing subsequence and application

AU - Crochemore, Maxime

AU - Porat, Ely

PY - 2010/9

Y1 - 2010/9

N2 - We consider the complexity of computing a longest increasing subsequence (LIS) parameterised by the length of the output. Namely, we show that the maximal length k of an increasing subsequence of a permutation of the set of integers {1, 2, ..., n) can be computed in time O(n log log k) in the RAM model, improving the previous 30-year bound of O(n log k). The algorithm also improves on the previous O(n log log n) bound. The optimality of the new bound is an open question. Reducing the computation of a longest common subsequence (LCS) between two strings to an LIS computation leads to a simple O(n log log n)-time algorithm for two sequences having r pairs of matching symbols and an LCS of length k. Crown Copyright (C) 2010 Published by Elsevier Inc. All rights reserved.

AB - We consider the complexity of computing a longest increasing subsequence (LIS) parameterised by the length of the output. Namely, we show that the maximal length k of an increasing subsequence of a permutation of the set of integers {1, 2, ..., n) can be computed in time O(n log log k) in the RAM model, improving the previous 30-year bound of O(n log k). The algorithm also improves on the previous O(n log log n) bound. The optimality of the new bound is an open question. Reducing the computation of a longest common subsequence (LCS) between two strings to an LIS computation leads to a simple O(n log log n)-time algorithm for two sequences having r pairs of matching symbols and an LCS of length k. Crown Copyright (C) 2010 Published by Elsevier Inc. All rights reserved.

U2 - 10.1016/j.ic.2010.04.003

DO - 10.1016/j.ic.2010.04.003

M3 - Article

VL - 208

SP - 1054

EP - 1059

JO - INFORMATION AND COMPUTATION

JF - INFORMATION AND COMPUTATION

IS - 9

ER -