Article ID Journal Published Year Pages File Type
6874754 Journal of Discrete Algorithms 2018 10 Pages PDF
Abstract
There exist many optimal (using single and multiple processors) and approximate solutions to the longest increasing subsequence (LIS) problem. Through this paper, we present the enhancement to the divide-and-conquer approach presented in paper [1]. An improved D&C algorithmic solution is proposed which outputs optimal solution in all cases. The proposed algorithm takes O(nlog⁡n) time in best and average cases and o(nlog2⁡n) time in worst case. The portion of the proposed solution can run in parallel using multiprocessors.
Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics
Authors
, ,