Labeling Schemes for Dynamic Tree Networks

Distance labeling schemes are composed of a marker algorithm forlabeling the vertices of a graph with short labels, coupled with adecoder algorithm allowing one to compute the distance betweenany two vertices directly from their labels (without using any additionalinformation).As applications for distance labeling schemesconcern mainly large and dynamically changing networks,it is of interest to study distributed dynamic labeling schemes.The current paper considers the problem on dynamic trees,and proposes efficient distributed schemes for it.The paper first presents a labeling scheme for distances in the dynamictree model, with amortized message complexity O(log² n) per operation,where n is the size of the tree at the time the operation takes place.The protocol maintains O(log² n) bit labels.This label size is known to be optimal even in the static scenario.A more general labeling scheme is then introduced for the dynamic treemodel, based on extending an existing static tree labelingscheme to the dynamic setting. The approach fits a number ofnatural tree functions, such as distance, separation level, and flow.The main resulting scheme incurs an overheadof an O(log n) multiplicative factor in both the label size andamortized message complexity in the case of dynamically growingtrees (with no vertex deletions).If an upper bound on n is known in advance,this method yields a different tradeoff, with anO(log² n/log log n) multiplicative overhead on the labelsize but only an O(log n/log log n) overhead on the amortizedmessage complexity. In the fully dynamic model the scheme also incurs an increasedadditive overhead in amortized communication, of O(log² n)messages per operation.