Murdoch University Research Repository

Welcome to the Murdoch University Research Repository

The Murdoch University Research Repository is an open access digital collection of research
created by Murdoch University staff, researchers and postgraduate students.

Learn more

PRAM algorithms for identifying polygon similarity

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

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 Item Control Page