Catalog Home Page

V-Order: New combinatorial properties & a simple comparison algorithm

Alatabbi, A., Daykin, J.W., Kärkkäinen, J., Sohel Rahman, M. and Smyth, W.F. (2016) V-Order: New combinatorial properties & a simple comparison algorithm. Discrete Applied Mathematics, 215 . pp. 41-46.

Link to Published Version:
*Subscription may be required


V-order is a global order on strings related to Unique Maximal Factorization Families (UMFFs), themselves generalizations of Lyndon words. VV-order has recently been proposed as an alternative to lexicographic order in the computation of suffix arrays and in the suffix-sorting induced by the Burrows–Wheeler transform. Efficient VV-ordering of strings thus becomes a matter of considerable interest. In this paper we discover several new combinatorial properties of VV-order, then explore the computational consequences; in particular, a fast, simple on-line VV-order comparison algorithm that requires no auxiliary data structures.

Item Type: Journal Article
Murdoch Affiliation: School of Engineering and Information Technology
Publisher: Elsevier BV
Copyright: © 2016 Elsevier B.V.
Item Control Page Item Control Page