On the longest increasing subsequence of a circular list
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).
|Combinatorial problems, Randomized algorithms|
|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