HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation
Conference papers

Compressed Representations of Permutations, and Applications

Abstract : We 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.
Document type :
Conference papers
Complete list of metadata

https://hal.inria.fr/inria-00358018
Contributor : Publications Loria Connect in order to contact the contributor
Submitted on : Monday, February 2, 2009 - 3:43:46 PM
Last modification on : Wednesday, May 6, 2020 - 8:18:02 PM
Long-term archiving on: : Tuesday, June 8, 2010 - 9:50:11 PM

Files

barbay_new.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : inria-00358018, version 1
  • ARXIV : 0902.1038

Collections

Citation

Jérémy Barbay, Gonzalo Navarro. Compressed Representations of Permutations, and Applications. 26th International Symposium on Theoretical Aspects of Computer Science STACS 2009, Feb 2009, Freiburg, Germany. pp.111-122. ⟨inria-00358018⟩

Share

Metrics

Record views

52

Files downloads

342