G.: A framework for succinct labeled ordinal trees over large alphabets

Abstract. We consider succinct representations of labeled ordinal trees that support a rich set of operations. Our new representations support a much broader collection of operations than previous work [10, 8, 1]. In our approach, labels of nodes are stored in a preorder label sequence, which can be compressed using any succinct index for strings that supports rankα and selectα operations. In other words, we present a framework for succinct representations of labeled ordinal trees that allows alphabets to be large. This answers an open problem presented by Geary et al. [10]. We further extend our work and present the first succinct representation of dynamic labeled ordinal trees that supports several label-based oper-ations including finding the level ancestor with a given label.