Blog
About

81
views
0
recommends
+1 Recommend
1 collections
    0
    shares
      • Record: found
      • Abstract: found
      • Article: found
      Is Open Access

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

      ,

      Visions of Computer Science - BCS International Academic Conference (VOCS)

      BCS International Academic Conference

      22 - 24 September 2008

      esign and analysis of algorithms, Longest increasing subsequence, Data structures, Priority BCS International queue

      Read this article at

      Bookmark
          There is no author summary for this article yet. Authors can add summaries to their articles on ScienceOpen to make them more accessible to a non-specialist audience.

          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.

          Related collections

          Most cited references 11

          • Record: found
          • Abstract: not found
          • Article: not found

          Alignment of whole genomes

            Bookmark
            • Record: found
            • Abstract: not found
            • Article: not found

            Design and implementation of an efficient priority queue

              Bookmark
              • Record: found
              • Abstract: not found
              • Article: not found

              A fast algorithm for computing longest common subsequences

                Bookmark

                Author and article information

                Contributors
                Conference
                September 2008
                September 2008
                : 69-74
                Affiliations
                King’s College London, Strand, London WC2R 2LS, UK

                and Université Paris-Est.
                Bar-Ilan University, Ramat-Gan 52900, Israel
                Article
                10.14236/ewic/VOCS2008.7
                © MAXIME CROCHEMORE et al. Published by BCS Learning and Development Ltd. Visions of Computer Science - BCS International Academic Conference

                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/

                Visions of Computer Science - BCS International Academic Conference
                VOCS
                Imperial College, London, UK
                22 - 24 September 2008
                Electronic Workshops in Computing (eWiC)
                BCS International Academic Conference
                Product
                Product Information: 1477-9358 BCS Learning & Development
                Self URI (journal page): https://ewic.bcs.org/
                Categories
                Electronic Workshops in Computing

                Comments

                Comment on this article