Abstract
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.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Ausiello, G., Crescenzi, P., Gambosi, G., Kann, V., Spaccamela, A.M., Protasi, M.: Complexity and approximation. Springer, Heidelberg (1999)
Borodin, A., El-Yaniv, R.: Online computation and competitive analysis. Cambridge University press, Cambridge (1998)
Hochbaum, D.: Approximation algorithms for NP-hard problems. PWS publishing company (1997)
Imase, M., Waxman, B.: Dynamic steiner tree problem. SIAM J. Discr. Math. 4, 369–384 (1991)
Laforest, C.: A good balance between weight and distances for multipoint trees. In: International Conference On Principles Of DIstributed Systems, pp. 195–204 (2002)
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)
Thibault, N., Laforest, C.: An optimal rebuilding strategy for an incremental tree problem. Journal of interconnection networks (submitted, 2004)
Waxman, B.: Routing of multipoint connections. IEEE Journal on Selected Areas in Communications 6, 1617–1622 (1988)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2006 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Thibault, N., Laforest, C. (2006). An Optimal Rebuilding Strategy for a Decremental Tree Problem. In: Flocchini, P., Gąsieniec, L. (eds) Structural Information and Communication Complexity. SIROCCO 2006. Lecture Notes in Computer Science, vol 4056. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11780823_13
Download citation
DOI: https://doi.org/10.1007/11780823_13
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-35474-1
Online ISBN: 978-3-540-35475-8
eBook Packages: Computer ScienceComputer Science (R0)