Labeling Schemes for Tree RepresentationReport as inadecuate

Labeling Schemes for Tree Representation - Download this document for free, or read online. Document in PDF available to download.

1 Department of Computer Science and Applied Mathematics Rehovot 2 LRI - Laboratoire de Recherche en Informatique

Abstract : This paper deals with compact label-based representations for trees. Consider an $n$-node undirected connected graph $G$ with a predefined numbering on the ports of each node. The {\em all-ports} tree labeling $\cL {all}$ gives each node $v$ of $G$ a label containing the port numbers of all the {\em tree} edges incident to $v$. The {\em upward} tree labeling $\cL {up}$ labels each node $v$ by the number of the port leading from $v$ to its parent in the tree. Our measure of interest is the worst case and total length of the labels used by the scheme, denoted $M {up}T$ and $S {up}T$ for $\cL {up}$ and $M {all}T$ and $S {all}T$ for $\cL {all}$. The problem studied in this paper is the following: Given a graph $G$ and a predefined port labeling for it, with the ports of each node $v$ numbered by $0,\ldots,\degv-1$, select a rooted spanning tree for $G$ minimizing one of these measures. We show that the problem is polynomial for $M {up}T$, $S {up}T$ and $S {all}T$ but NP-hard for $M {all}T$ even for 3-regular planar graphs. We show that for every graph $G$ and port numbering there exists a spanning tree $T$ for which $S {up}T = On\log\log n$. We give a tight bound of $On$ in the cases of complete graphs with arbitrary labeling and arbitrary graphs with symmetric port assignments. We conclude by discussing some applications for our tree representation schemes.

Keywords : Labeling scheme spanning tree tree representation

Author: Reuven Cohen - Pierre Fraigniaud - David Ilcinkas - Amos Korman - David Peleg -



Related documents