PRAM algorithms for identifying polygon similarity
Tools
Tools
Tools
Iliopoulos, C.S. and Smyth, W.F. (1989) PRAM algorithms for identifying polygon similarity. Lecture Notes in Computer Science, 401 . pp. 25-32.
Link to Published Version: http://dx.doi.org/10.1007/3-540-51859-2_4
*Subscription may be required
*Subscription may be required
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.
| Item Type: | Journal Article |
|---|---|
| Publisher: | Springer Verlag |
| Copyright: | 2005 Springer-Verlag |
| URI: | http://researchrepository.murdoch.edu.au/id/eprint/27447 |
 |
Item Control Page |