Tree path majority data structures

DOI10.1016/J.TCS.2020.05.039MaRDI QIDQ784481zbMATH OpenOpenAlexFDO

Authors Travis Gagie, Meng He, Gonzalo Navarro, Carlos Ochoa

Publication date 3 August 2020

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

Full work available at URL https://drops.dagstuhl.de/opus/volltexte/2018/10016/

zbMATH Keywords

succinct data structuresmajorities on trees

Mathematics Subject Classification ID

Trees (05C05) Data structures (68P05) Paths and cycles (05C38)

Recommendations

• Optimal encodings for range majority queries
• Compressed dynamic range majority and minority data structures
• Data structures for path queries
• Succinct Data Structures for Path Queries
• Range majorities and minorities in arrays

Cites work

• scientific article; zbMATH DE number 1947405 (Why is no real title available?)
• scientific article; zbMATH DE number 2119724 (Why is no real title available?)
• scientific article; zbMATH DE number 2226802 (Why is no real title available?)
• A data structure for dynamic trees
• A framework for succinct labeled ordinal trees over large alphabets
• Alphabet-independent compressed text indexing
• Better space bounds for parameterized range majority and minority
• Computing on a free tree via complexity-preserving mappings
• Finding repeated elements
• Fully compressed suffix trees
• Fully functional static and dynamic succinct trees
• Linear-space data structures for range frequency queries on arrays and trees
• Linear-space data structures for range minority query in arrays
• Linear-space data structures for range mode query in arrays
• Lowest common ancestors in trees and directed acyclic graphs
• Optimal lower and upper bounds for representing sequences
• Path queries on functions
• Succinct indexable dictionaries with applications to encoding \(k\)-ary trees, prefix sums and multisets
• Succinct indices for path minimum, with applications
• Succinct representation of labeled trees
• The level ancestor problem simplified

Cited in

(2)

• Path queries on functions
• Path queries on functions

This page was built for publication: Tree path majority data structures

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q784481)