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.