Compact separator decompositions in dynamic trees and applications to labeling schemes

摘要: This paper presents an efficient scheme maintaining a separator decomposition representation in dynamic trees using asymptotically optimal labels. In order to maintain the short labels, uses relatively low message complexity. particular, if initial tree contains just root, then incurs O(log3 n) amortized complexity per topology change, where n is current number of nodes tree. As fundamental used extensively as component many static graph algorithms, our for may be constructing versions these algorithms. The shows how use construct rather labeling schemes on trees, same scheme. Specifically, we routing both designer and adversary port models, which up multiplicative factor O(log log n). addition, it shown supporting ancestry NCA relations well extend known result distance schemes.