Succinct data structures for nearest colored node in a tree

摘要

We give succinct data structures that store a tree with colors on the nodes. Given a node x and a color alpha, the structures find the nearest node to x with color alpha. Our results improve the O(n log n)-bits structure of Gawrychowski et al. (2016) [12]. (C) 2017 Elsevier B.V. All rights reserved.