We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
Compact separator decompositions in dynamic trees and applications to labeling schemes.
- Authors
Korman, Amos; Peleg, David
- Abstract
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, the scheme uses relatively low message complexity. In particular, if the initial dynamic tree contains only the root, then the scheme incurs an O(log4 n) amortized message complexity per topology change, where n is the current number of vertices in the tree. As a separator decomposition is a fundamental decomposition of trees used extensively as a component in many static graph algorithms, our dynamic scheme for separator decomposition may be used for constructing dynamic versions to these algorithms. The paper then shows how to use our dynamic separator decomposition to construct efficient labeling schemes on dynamic trees, using the same message complexity as our dynamic separator scheme. Specifically, we construct efficient routing schemes on dynamic trees, for both the designer and the adversary port models, which maintain optimal labels, up to a multiplicative factor of O(log log n). In addition, it is shown how to use our dynamic separator decomposition scheme to construct dynamic labeling schemes supporting the ancestry and NCA relations using asymptotically optimal labels, as well as to extend a known result on dynamic distance labeling schemes.
- Subjects
DATA structures; TOPOLOGICAL graph theory; TREE graphs; MACHINE-readable bibliographic data formats; GRAPH algorithms
- Publication
Distributed Computing, 2008, Vol 21, Issue 2, p141
- ISSN
0178-2770
- Publication type
Article
- DOI
10.1007/s00446-008-0061-5