Computing a Longest Increasing Subsequence of Length  k  in Time  O ( n  log log  k )

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.

Content

Author and article information

Contributors

MAXIME CROCHEMORE

ELY PORAT

Conference

Publication date: September 2008

Publication date (Print): September 2008

Pages: 69-74

Affiliations

[0001]King’s College London, Strand, London WC2R 2LS, UK

and Université Paris-Est.

[0002]Bar-Ilan University, Ramat-Gan 52900, Israel

Article

DOI: 10.14236/ewic/VOCS2008.7

SO-VID: 3eda0c27-337c-43f2-abba-2ae739308e42

License:

This work is licensed under a Creative Commons Attribution 4.0 Unported License. To view a copy of this license, visit http://creativecommons.org/licenses/by/4.0/

Conference name: Visions of Computer Science - BCS International Academic Conference

Conference acronym: VOCS

Conference number:

Conference location: Imperial College, London, UK

Conference date: 22 - 24 September 2008

Conference sponsor: Electronic Workshops in Computing (eWiC)

Conference theme: BCS International Academic Conference

History

Product

1477-9358 BCS Learning & Development

Self URI (article page): https://www.scienceopen.com/hosted-document?doi=10.14236/ewic/VOCS2008.7

Self URI (journal page): https://ewic.bcs.org/

Celebrating 65 years of The Computer Journal - free-to-read perspectives - bcs.org/tcj65

Computing a Longest Increasing Subsequence of Length k in Time O( n log log k)

Abstract