General compact labeling schemes for dynamic trees

amortized message complexity decoder algorithm distributed algorithms dynamic labeling schemes dynamic networks dynamic trees function on pairs of vertices label size leaf-dynamic tree model leaf-inceasing model marker algorithm routing schemes

Mathematics Subject Classification ID

Trees (05C05) Graph algorithms (graph-theoretic aspects) (05C85) Distributed algorithms (68W15)

Abstract: 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 (l o g_{k (n)} n)

on the label size and

O (k (n) l o g_{k (n)} n)

on the amortized message complexity. In particular, by setting

k (n) = n^{e p s i l o n}

for any

0 < e p s i l o n < 1

, we obtain dynamic labeling schemes with asymptotically optimal label sizes and sublinear amortized message complexity for all the above mentioned functions.

Recommendations

Cites work

Cited in

(15)

This page was built for publication: General compact labeling schemes for dynamic trees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1954239)