3 citations · 3 across the 4 of their papers we have counts for
4 papers
Near-optimal adjacency labeling scheme for power-law graphs
Casper Petersen, Noy Rotbart, Jakob Grue Simonsen +1
An adjacency labeling scheme is a method that assigns labels to the vertices of a graph such that adjacency between vertices can be inferred directly from the assigned label, witho…
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…
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…
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…