Name
Abstract | ||
|---|---|---|
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(n^3^/^2logn) and storage requirement O(n). It is proved that the expected length @m(n) of the LICS satisfies lim"n"-"~@m(n)2n=1. Numerical experiments with the algorithm suggest that |@m(n)-2n|=O(n^1^/^6). |
Year | DOI | Venue |
|---|---|---|
2007 | 10.1016/j.ipl.2006.08.003 | Inf. Process. Lett. |
Keywords | Field | DocType |
worst case execution time,numerical experiment,expected length,monte carlo algorithm,circular subsequence,circular list,storage requirement o,randomized algorithm,longest increasing subsequence,randomized algorithms,satisfiability | Discrete mathematics,Randomized algorithm,Combinatorics,Monte Carlo method,Longest increasing subsequence,Worst-case execution time,Monte Carlo algorithm,Execution time,Subsequence,Mathematics | Journal |
Volume | Issue | ISSN |
101 | 2 | 0020-0190 |
Citations | PageRank | References |
7 | 0.54 | 2 |
Authors | ||
5 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| M H Albert | 1 | 79 | 8.32 |
| M. D. Atkinson | 2 | 53 | 4.85 |
| Doron Nussbaum | 3 | 89 | 13.49 |
| Jörg-Rüdiger Sack | 4 | 1099 | 166.07 |
| Nicola Santoro | 5 | 7 | 0.54 |