MSc Thesis Defense by Søren Dahlgaard

Title

Labeling schemes for adjacency and large distances   

Abstract

In this thesis I consider the field of informative labeling schemes introduced by Kannan et al. [STOC’88]. I address two problems in this model. The first is the problem of D-preserving distance labeling schemes introduced by Bollobás et al. [SODA’03]. A D-preserving distance labeling scheme assigns bit strings (labels) to the nodes of a graph such that given just the labels of two nodes u,v in some undirected and unweighted graph G, one is able to deduce the exact distance between u and v if they are at least distance D apart without the need for a centralized data structure. I show that a labeling scheme of size O((n/D)  log^2 D) exists for this problem, matching the lower bound of Bollobás et al. up to a factor of log D. The labeling scheme is based on sampling techniques and a new notion of sick nodes.

The second problem I consider is adjacency labeling in forests. An adjacency labeling scheme assigns labels to the nodes of a forest, such that given just the labels of two nodes u, v, one is able to determine whether u and v are adjacent or not. Recently, Alstrup et al. solved a long-standing open problem, showing that labels of size lg n + Θ(1) are sufficient. In this thesis I present an analysis of the algorithmic aspects of their labeling scheme, showing that it performs encoding (label assignment) in O(n) time and decoding (queries) in O(1) time, both of which are optimal.

Supervisor: Mikkel Thorup

Censor: Rolf Fagerberg