Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
6874754 | Journal of Discrete Algorithms | 2018 | 10 Pages |
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
Seema Rani, Dharmveer Singh Rajpoot,