Visions of Computer Science - BCS International Academic Conference

Imperial College, London, UK - 22 - 24 September 2008

AUTHORS

Maxime Crochemore & Ely Porat

ABSTRACT

We consider the complexity of computing a longest increasing subsequence 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 log n). The optimality of the new bound is an open question.

PAPER FORMATS 

PDF Version of this Paper (291kb)

 

Other Papers in this Session
Other Sessions in this Conference