General Compact Labeling Schemes for Dynamic Trees

by Amos Korman arXiv.org E-print Archive, 30 May 2006 Let F be a function on pairs of vertices. An F- labeling scheme is composed of a marker algorithm for labeling the vertices of a graph with short labels, coupled with a decoder algorithm allowing one to compute F(u, v) of any two vertices u and v directly from their labels. As applications for labeling schemes concern mainly large and dynamically changing networks, it is of interest to study distributed dynamic labeling schemes. This paper investigates labeling schemes for dynamic trees. We consider two dynamic tree models, namely, the leaf-dynamic tree model in which at each step a leaf can be added to or removed from the tree and the leaf-increasing tree model in which the only topological event that may occur is that a leaf joins the tree. Read more