Journal article
PRAM algorithms for identifying polygon similarity
Optimal Algorithms, Vol.401, pp.25-32
1989
Abstract
The computation of the least lexicographic rotation of a string leads to the identification of polygon similarity. An O(logn) time CRCW PRAM algorithm for computing the least lexicographic rotation of a circular string (of length n) over a fixed alphabet is presented here. The logarithmic running time is achieved by using O(n/logn) processors and its space complexity is linear. A second algorithm for unbounded alphabets requires O(lognloglogn) units of time, uses O(n/logn) processors.
Details
- Title
- PRAM algorithms for identifying polygon similarity
- Authors/Creators
- C.S. Iliopoulos (Author/Creator) - Royal Holloway University of LondonW.F. Smyth (Author/Creator) - McMaster University
- Publication Details
- Optimal Algorithms, Vol.401, pp.25-32
- Publisher
- Springer Verlag
- Identifiers
- 991005545564407891
- Copyright
- 2005 Springer-Verlag
- Murdoch Affiliation
- Murdoch University
- Language
- English
- Resource Type
- Journal article
Metrics
70 Record Views