An Optimal Rebuilding Strategy for a Decremental Tree Problem
- 387 Downloads
This paper is devoted to the following decremental problem. Initially, a graph and a distinguished subset of vertices, called initial group, are given. This group is connected by an initial tree. The decremental part of the input is given by an on-line sequence of withdrawals of vertices of the initial group, removed on-line one after one. The goal is to keep connected each successive group by a tree, satisfying a quality constraint: The maximum distance (called diameter) in each constructed tree must be kept in a given range compared to the best possible one. Under this quality constraint, our objective is to minimize the number of critical stages of the sequence of constructed trees. We call “critical” a stage where the current tree is rebuilt. We propose a strategy leading to at most O(logi) critical stages (i is the number of removed members). We also prove that there exist situations where Ω(logi) critical stages are necessary to any algorithm to maintain the quality constraint. Our strategy is then worst case optimal in order of magnitude.
Unable to display preview. Download preview PDF.
- 3.Hochbaum, D.: Approximation algorithms for NP-hard problems. PWS publishing company (1997)Google Scholar
- 5.Laforest, C.: A good balance between weight and distances for multipoint trees. In: International Conference On Principles Of DIstributed Systems, pp. 195–204 (2002)Google Scholar
- 6.Raghavan, S., Manimaran, G., Murthy, C.S.R.: A rearrangeable algorithm for the construction of delay-constrained dynamic multicast trees. In: IEEE/ACM (SIGCOMM), vol. 7, ACM Press, New York (1999)Google Scholar
- 7.Thibault, N., Laforest, C.: An optimal rebuilding strategy for an incremental tree problem. Journal of interconnection networks (submitted, 2004)Google Scholar