Labeling schemes for weighted dynamic trees

摘要: This paper studies β-approximate distance labeling schemes, which are composed of a marker algorithm for the vertices graph with short labels, coupled decoder allowing one to compute β-approximation between any two directly from their labels (without using additional information). As most applications informative schemes in general, and particular, concern large dynamically changing networks, it is interest focus on distributed dynamic schemes. The considers problem weighted trees cycles where tree (or cycle) fixed but (positive integral) weights edges may change. models considered fully model, time some edge changes its weight by quanta, increasing model can only grow. presents models, β > 1, establishes upper lower bounds required label size communication complexity involved updating following