Skip to Main content Skip to Navigation
Conference papers

Computing a longest increasing subsequence of length k in time O(n\log\log k)

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.
Document type :
Conference papers
Complete list of metadatas

Cited literature [16 references]  Display  Hide  Download

https://hal-upec-upem.archives-ouvertes.fr/hal-00620279
Contributor : Maxime Crochemore <>
Submitted on : Thursday, February 14, 2013 - 8:33:23 AM
Last modification on : Wednesday, February 26, 2020 - 7:06:05 PM
Long-term archiving on: : Wednesday, May 15, 2013 - 2:40:09 AM

File

ewic_vs08_s2paper2.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-00620279, version 1

Citation

Maxime Crochemore, Ely Porat. Computing a longest increasing subsequence of length k in time O(n\log\log k). Visions of computer science, 2008, Swindon, UK, United Kingdom. pp.69-74. ⟨hal-00620279⟩

Share

Metrics

Record views

272

Files downloads

294