# zbMATH — the first resource for mathematics

Succinct data structures for path queries. (English) Zbl 1365.68181
Epstein, Leah (ed.) et al., Algorithms – ESA 2012. 20th annual European symposium, Ljubljana, Slovenia, September 10–12, 2012. Proceeding. Berlin: Springer (ISBN 978-3-642-33089-6/pbk). Lecture Notes in Computer Science 7501, 575-586 (2012).
Summary: Consider a tree $$T$$ on $$n$$ nodes, each having a weight drawn from $$[1..\sigma ]$$. In this paper, we design succinct data structures to encode $$T$$ using $$n H(W_T) + o(n\lg \sigma)$$ bits of space, such that we can support path counting queries in $$O(\frac{\lg \sigma}{\lg\lg n} + 1)$$ time, path reporting queries in $$O((\mathrm{occ}+1)(\frac{\lg \sigma}{\lg\lg n} + 1))$$ time, and path median and path selection queries in $$O(\frac{\lg \sigma}{\lg\lg \sigma})$$ time, where $$H(W _{T })$$ is the entropy of the multiset of the weights of the nodes in $$T$$. Our results not only improve the best known linear space data structures [the authors, Lect. Notes Comput. Sci. 7074, 140–149 (2011; Zbl 1350.68073)], but also match the lower bounds for these path queries [M. Pǎtraşcu, in: Proceedings of the 39th annual ACM symposium on theory of computing, STOC’07. New York, NY: Association for Computing Machinery (ACM). 40–46 (2007; Zbl 1232.68068); SIAM J. Comput. 40, No. 3, 827–847 (2011; Zbl 1226.68033); A. G. Jørgensen and K. G. Larsen, in: Proceedings of the 22nd annual ACM-SIAM symposium on discrete algorithms, SODA’11. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM). 805–813 (2011; doi:10.1137/1.9781611973082.63)] when $$\sigma = \Omega(n / \text{polylog}(n))$$.
For the entire collection see [Zbl 1246.68031].

##### MSC:
 68P05 Data structures
Full Text: