29 września 2016 12:15
Seminarium ZZOiAA: Paweł Gawrychowski, Labeling schemes for trees
Labeling schemes seek to assign a short label (bit string) to each
vertex in a graph, so that a function on two nodes can be computed by
examining their labels alone. This is particularly desirable in
distributed settings, where nodes are often processed using only some
locally stored data. Probably the most natural example of such
function is the distance. It was known that labeling the nodes of a
tree on n nodes for distance queries requires 1/4log^2n bits and can
be done using 1/2log^2n bits. We show that, in fact,
1/4log^2n+o(log^2n) is enough, thus closing the gap. We also consider
computing approximate distances in different variants. Another natural
example is the nearest common ancestor (NCA). In this case we
additionally require that the labels are all distinct, and given the
labels of two nodes we can compute the label of their NCA. It was
known that 2.772logn bits are enough and 1.008logn bits are required.
We substantially improve the lower bound and argue that, for a certain
class of labeling schemes based on defining a universal tree, it is
almost optimal. I will also briefly survey other labeling problems, in
particular describe a couple of open questions suitable for a Master's
thesis.
Joint work with Ofer Freedman, Jakub Łopuszański, Pat Nicholson, and
Oren Weimann.