3 papers
cs.DS2014
A simple and optimal ancestry labeling scheme for trees
Søren Dahlgaard, Mathias Bæk Tejs Knudsen, Noy Rotbart
We present a ancestry labeling scheme for trees. The problem was first presented by Kannan et al. [STOC 88'] along with a simple solution. Motivat…
cs.DS2014
Dynamic and Multi-functional Labeling Schemes
Søren Dahlgaard, Mathias Bæk Tejs Knudsen, Noy Rotbart
We investigate labeling schemes supporting adjacency, ancestry, sibling, and connectivity queries in forests. In the course of more than 20 years, the existence of $\log n + O(\log…
cs.DM2014
Labeling Schemes for Bounded Degree Graphs
David Adjiashvili, Noy Rotbart
We investigate adjacency labeling schemes for graphs of bounded degree . In particular, we present an optimal (up to an additive constant) adjacency labeli…