General Compact Labeling Schemes for Dynamic Trees

Details General Compact Labeling Schemes for Dynamic Trees General Compact Labeling Schemes for Dynamic Trees

2006-05-30

arxiv.org/abs/cs/0605141v1

Computer Science

Distributed, Parallel, and Cluster Computing

32 pages, no figures, the extended abstarct appeired in DISC 2005

Scientific paper

Let $F$ be a function on pairs of vertices. An {\em $F$- labeling scheme} is composed of a {\em marker} algorithm for labeling the vertices of a graph with short labels, coupled with a {\em 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 {\em distributed dynamic} labeling schemes. This paper investigates labeling schemes for dynamic trees. This paper presents a general method for constructing labeling schemes for dynamic trees. Our method is based on extending an existing {\em static} tree labeling scheme to the dynamic setting. This approach fits many natural functions on trees, such as ancestry relation, routing (in both the adversary and the designer port models), nearest common ancestor etc.. Our resulting dynamic schemes incur overheads (over the static scheme) on the label size and on the communication complexity. Informally, for any function $k(n)$ and any static $F$-labeling scheme on trees, we present an $F$-labeling scheme on dynamic trees incurring multiplicative overhead factors (over the static scheme) of $O(\log_{k(n)} n)$ on the label size and $O(k(n)\log_{k(n)} n)$ on the amortized message complexity. In particular, by setting $k(n)=n^{\epsilon}$ for any $0<\epsilon<1$, we obtain dynamic labeling schemes with asymptotically optimal label sizes and sublinear amortized message complexity for all the above mentioned functions.

Affiliated with

Also associated with

No associations

Rating

General Compact Labeling Schemes for Dynamic Trees does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with General Compact Labeling Schemes for Dynamic Trees, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and General Compact Labeling Schemes for Dynamic Trees will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-467170