2007-01-31
On the longest increasing subsequence of a circular list
Publication
Publication
Information Processing Letters , Volume 101 - Issue 2 p. 55- 59
The longest increasing circular subsequence (LICS) of a list is considered. A Monte Carlo algorithm to compute it is given which has worst case execution time O (n3 / 2 log n) and storage requirement O (n). It is proved that the expected length μ (n) of the LICS satisfies limn → ∞ frac(μ (n), 2 sqrt(n)) = 1. Numerical experiments with the algorithm suggest that | μ (n) - 2 sqrt(n) | = O (n1 / 6).
| Additional Metadata | |
|---|---|
| Combinatorial problems, Randomized algorithms | |
| dx.doi.org/10.1016/j.ipl.2006.08.003 | |
| Information Processing Letters | |
| Organisation | School of Computer Science |
|
Albert, M.H., Atkinson, M.D., Nussbaum, D, Sack, J.-R, & Santoro, N. (2007). On the longest increasing subsequence of a circular list. Information Processing Letters, 101(2), 55–59. doi:10.1016/j.ipl.2006.08.003
|
|