Succinct representations of weighted trees supporting path queries

DOI10.1016/j.jda.2012.08.003zbMath1268.68069MaRDI QIDQ2376795

Rahul Shah, Manish Patil, 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

05C05: Trees

68R10: Graph theory (including graph drawing) in computer science

68P05: Data structures

Related Items

Linear-space data structures for range frequency queries on arrays and trees, Dynamic path queries in linear space, Data structures for categorical path counting queries, Succinct indices for path minimum, with applications, Range selection and predecessor queries in data aware space and time, Array Range Queries

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Representing trees of higher degree
• Computing on a free tree via complexity-preserving mappings
• Parallel preprocessing for path queries without concurrent reading.
• An O(nlog n) Algorithm for the Maximum Agreement Subtree Problem for Binary Trees
• Succinct Representation of Balanced Parentheses and Static Trees
• Path Queries in Weighted Trees
• Fast Algorithms for Finding Nearest Common Ancestors
• Position-Restricted Substring Searching
• Balanced parentheses strike back