Compressed Representations of Permutations, and Applications

Simple item page
dc.creatorBarbay, Jérémy
dc.creatorNavarro, Gonzalo
dc.date2009-02-06
dc.date.accessioned2026-07-07T12:38:53Z
dc.date.available2026-07-07T12:38:53Z
dc.descriptionWe explore various techniques to compress a permutation $π$ over n integers, taking advantage of ordered subsequences in $π$, while supporting its application $π$(i) and the application of its inverse $π^{-1}(i)$ in small time. Our compression schemes yield several interesting byproducts, in many cases matching, improving or extending the best existing results on applications such as the encoding of a permutation in order to support iterated applications $π^k(i)$ of it, of integer functions, and of inverted lists and suffix arrays.
dc.identifierhttps://arxiv.org/abs/0902.1038
dc.identifierhttp://arxiv.org/abs/0902.1038
dc.identifierSTACS 2009 (2009) 111-122
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/218923
dc.subjectData Structures and Algorithms
dc.titleCompressed Representations of Permutations, and Applications
dc.typetext

Files

Collections

arXiv