Succinct representations of permutations and functions

DOI10.1016/j.tcs.2012.03.005zbMath1245.68075arXiv1108.1983OpenAlexW1987699222MaRDI QIDQ441860

J. Ian Munro, Rajeev Raman, S. Srinivasa Rao, Venkatesh Raman

Publication date: 8 August 2012

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1108.1983

zbMATH Keywords

permutationsfunctionssuccinct data structuresbenes networklevel ancestor queriesspace redundancysuccinct tree representations

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Data structures (68P05)

Related Items (27)

Adjacency Labeling Schemes and Induced-Universal Graphs ⋮ Grammar-compressed indexes with logarithmic search time ⋮ Representation of ordered trees with a given degree distribution ⋮ Succinct encodings for families of interval graphs ⋮ The function-inversion problem: barriers and opportunities ⋮ Parallel construction of succinct trees ⋮ Lempel Ziv Computation in Small Space (LZ-CISS) ⋮ On compressing permutations and adaptive sorting ⋮ Compact representations of spatial hierarchical structures with support for topological queries ⋮ Succinct data structure for dynamic trees with faster queries ⋮ Coding for locality in reconstructing permutations ⋮ Space-efficient algorithms for computing minimal/shortest unique substrings ⋮ Distance-based index structures for fast similarity search ⋮ GraCT: a grammar-based compressed index for trajectory data ⋮ Efficient fully-compressed sequence representations ⋮ Succinct representation of labeled trees ⋮ Extra Space during Initialization of Succinct Data Structures and Dynamical Initializable Arrays. ⋮ A Self-index on Block Trees ⋮ Path queries on functions ⋮ Simple and efficient fully-functional succinct trees ⋮ Fast compressed self-indexes with deterministic linear-time construction ⋮ Unnamed Item ⋮ Sampling Lower Bounds: Boolean Average-Case and Permutations ⋮ An Audit Tool for Genome Rearrangement Algorithms ⋮ A Space-Optimal Grammar Compression. ⋮ Succinct representation for (non)deterministic finite automata ⋮ From Time to Space: Fast Algorithms That Yield Small and Fast Data Structures

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Representing trees of higher degree
• A simple optimal representation for balanced parentheses
• Efficient representation of perm groups
• Finding level-ancestors in trees
• Min-wise independent permutations
• Log-logarithmic worst-case range queries are possible in space theta(N)
• The cell probe complexity of succinct data structures
• Optimal lower bounds for rank and select indexes
• Succinct Representation of Balanced Parentheses and Static Trees
• Changing base without losing space
• Succinct ordinal trees with level-ancestor queries
• Compressed suffix arrays and suffix trees with applications to text indexing and string matching (extended abstract)
• Rank/select operations on large alphabets
• A cryptanalytic time-memory trade-off
• Succinct Indexable Dictionaries with Applications to Encoding $k$-ary Trees, Prefix Sums and Multisets
• COMPRESSED REPRESENTATIONS OF PERMUTATIONS, AND APPLICATIONS
• Succinct Ordinal Trees Based on Tree Covering
• On the number of permutations admitting an \(m\)th root

This page was built for publication: Succinct representations of permutations and functions