Succinct representations of weighted trees supporting path queries

DOI10.1016/J.JDA.2012.08.003MaRDI QIDQ2376795zbMATH OpenOpenAlexFDO

Authors Manish Patil, Rahul Shah, Sharma V. Thankachan

Publication date 24 June 2013

Published in Journal of Discrete Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.jda.2012.08.003

zbMATH Keywords

succinct data structures

Mathematics Subject Classification ID

Trees (05C05) Graph theory (including graph drawing) in computer science (68R10) Data structures (68P05)

Recommendations

• Data structures for path queries
• Path queries in weighted trees
• Succinct Data Structures for Path Queries
• Succinct indices for path minimum, with applications
• Succinct indices for path minimum, with applications to path reporting

Cites work

• scientific article; zbMATH DE number 2079421 (Why is no real title available?)
• scientific article; zbMATH DE number 871936 (Why is no real title available?)
• scientific article; zbMATH DE number 2226802 (Why is no real title available?)
• An \(O(n\log n)\) algorithm for the maximum agreement subtree problem for binary trees
• Balanced parentheses strike back
• Computing on a free tree via complexity-preserving mappings
• Fast Algorithms for Finding Nearest Common Ancestors
• Parallel preprocessing for path queries without concurrent reading.
• Path queries in weighted trees
• Position-Restricted Substring Searching
• Representing trees of higher degree
• Succinct representation of balanced parentheses and static trees
• Ultra-succinct representation of ordered trees

Cited in

(14)

• Write it recursively
• Linear-space data structures for range frequency queries on arrays and trees
• Succinct indices for path minimum, with applications
• Succinct indices for path minimum, with applications to path reporting
• Data structures for path queries
• Path queries in weighted trees
• Array range queries
• Weighted hypertree decompositions and optimal query plans
• Data structures for categorical path counting queries
• Tree decomposition-based indexing for efficient shortest path and nearest neighbors query answering on graphs
• Dynamic path queries in linear space
• Forward node-selecting queries over trees
• Range selection and predecessor queries in data aware space and time
• Succinct Data Structures for Path Queries

This page was built for publication: Succinct representations of weighted trees supporting path queries

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