Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
436145 | Theoretical Computer Science | 2015 | 10 Pages |
Abstract
We give a representation for labeled ordered trees that supports labeled queries such as finding the i-th ancestor of a node with a given label. Our representation is succinct, namely the redundancy is small-o of the optimal space for storing the tree. This improves the representation of He et al. (ISAAC 2012) [8] which is succinct only when the entropy of the labels is ω(1)ω(1).
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Dekel Tsur,