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

A comparison of three optimal algorithms for the canonization of circular strings

Iliopoulos, C.S. and Smyth, W.F. (1989) A comparison of three optimal algorithms for the canonization of circular strings. Journal of Combinatorics, Information & System Sciences, 14 (2/3). pp. 59-72.


Every position i in a given circular string A of length n gives rise to a linear string A[i],...,A[n],A[1],···,A[i-1]. It is required to determine every position in A which begins a linear string that is lexicographically least over all linear strings of A. There are three quite different sequential algorithms, due to K. S. Booth [Inf. Process. Lett. 10, 240-242 (1980; Zbl 0444.68064)], Y. Shiloach [J. Algorithms 2, 107-121 (1981; Zbl 0459.68035)], and the authors [A new sequential algorithm for canonization of circular strings, submitted for publication], which solve this problem in O(n) time, and which are therefore asymptotically optimal. We provide overviews of these algorithms, together with an analysis of their performance in important cases; we also report on comparisons among them, based on two measures of complexity: number of “tests” and run time. The algorithms have application to computational geometry; in particular, to the determination of whether or not two given n-gons are similar.

Item Type: Journal Article
Publisher: MDPPL
Publisher's Website:
Item Control Page Item Control Page