An Optimal Rebuilding Strategy for a Decremental Tree Problem

  • Nicolas Thibault
  • Christian Laforest
Conference paper
Part of the Lecture Notes in Computer Science book series (LNCS, volume 4056)


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.

Unable to display preview. Download preview PDF.


  1. 1.
    Ausiello, G., Crescenzi, P., Gambosi, G., Kann, V., Spaccamela, A.M., Protasi, M.: Complexity and approximation. Springer, Heidelberg (1999)zbMATHGoogle Scholar
  2. 2.
    Borodin, A., El-Yaniv, R.: Online computation and competitive analysis. Cambridge University press, Cambridge (1998)zbMATHGoogle Scholar
  3. 3.
    Hochbaum, D.: Approximation algorithms for NP-hard problems. PWS publishing company (1997)Google Scholar
  4. 4.
    Imase, M., Waxman, B.: Dynamic steiner tree problem. SIAM J. Discr. Math. 4, 369–384 (1991)zbMATHCrossRefMathSciNetGoogle Scholar
  5. 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. 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. 7.
    Thibault, N., Laforest, C.: An optimal rebuilding strategy for an incremental tree problem. Journal of interconnection networks (submitted, 2004)Google Scholar
  8. 8.
    Waxman, B.: Routing of multipoint connections. IEEE Journal on Selected Areas in Communications 6, 1617–1622 (1988)CrossRefGoogle Scholar

Copyright information

© Springer-Verlag Berlin Heidelberg 2006

Authors and Affiliations

  • Nicolas Thibault
    • 1
  • Christian Laforest
    • 1
  1. 1.Tour Evry 2, LaMI/IBISCUniversité d’EvryEVRYFrance

Personalised recommendations