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 | |
|---|---|
| Keywords | Combinatorial problems, Randomized algorithms |
| Persistent URL | dx.doi.org/10.1016/j.ipl.2006.08.003 |
| Journal | Information Processing Letters |
| Citation |
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
|