Abstract of Paper

Informative Labeling Schemes for Graphs
by David Peleg

Abstract:

This paper introduces the notion of informative labeling schemes for graphs.
Let $f(W)$ be a function on vertex subsets $W$. An $f$ labeling scheme
labels the vertices of a weighted graph $G$ in such a way that $f(W)$ can be
inferred efficiently for any $W$ in $G$ by inspecting the labels of the
vertices of $W$, without having to use any additional information.

We first develop $f$ labeling schemes for three functions $f$ over the class
of $n$-vertex trees. The first function gives the the depth of the least
common ancestor of any two vertices in the tree. The second provides the
least common ancestor of any two vertices. The third yields the center of
any three given vertices $v_1$, $v_2$, $v_3$ in the tree, namely, the unique
vertex $z$ connected to them by edge-disjoint paths. All three labeling
schemes use $O(\log^2 n)$-bit labels, which is shown to be asymptotically
optimal. Our main results concern the function $Steiner(W)$, defined for
weighted graphs. For any vertex subset $W$ in the weighted graph $G$,
$Steiner(W)$ denotes the weight of the Steiner tree spanning vertices of $W$
in $G$. For the class of $n$-vertex trees with $M$-bit edge weights, it is
shown that there exists a $Steiner$ labeling scheme using $O((M+\log n)\log n)$ bit labels, which is asymptotically optimal. It is then shown that the
class of arbitrary $n$-vertex graphs with $M$-bit edge weights has an
$O(\sqrt{\log n})$ approximate $Steiner$ labeling scheme using $O((M+\log n)\log^2 n)$ bit labels.