Small Stretch Spanners on Dynamic Graphs | SpringerLink
Skip to main content
Springer Nature Link
Log in

Small Stretch Spanners on Dynamic Graphs

  • Conference paper
Algorithms – ESA 2005 (ESA 2005)

Part of the book series: Lecture Notes in Computer Science ((LNTCS,volume 3669))

Included in the following conference series:

  • 2350 Accesses

Abstract

We present fully dynamic algorithms for maintaining 3- and 5-spanners of undirected graphs. For unweighted graphs we maintain a 3- or 5-spanner under insertions and deletions of edges in O(n) amortized time per operation over a sequence of Ω(n) updates. The maintained 3-spanner (resp., 5-spanner) has O(n 3/2) edges (resp., O(n 4/3) edges), which is known to be optimal. On weighted graphs with d different edge cost values, we maintain a 3- or 5-spanner in O(n) amortized time per operation over a sequence of Ω(d n) updates. The maintained 3-spanner (resp., 5-spanner) has O(d n 3/2) edges (resp., O(d n 4/3) edges). The same approach can be extended to graphs with real-valued edge costs in the range [1,C]. All our algorithms are deterministic and are substantially faster than recomputing a spanner from scratch after each update.

Partially supported by the Italian MIUR Project ALGO-NEXT “Algorithms for the Next Generation Internet and Web: Methodologies, Design and Experiments”.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. Althofer, I., Das, G., Dobkin, D.P., Joseph, D., Soares, J.: On sparse spanners of weighted graphs. Discrete & Computational Geometry 9, 81–100 (1993)

    Article  MathSciNet  Google Scholar 

  2. Awerbuch, B.: Complexity of network synchronization. Journal of the ACM 32(4), 804–823 (1985)

    Article  MATH  MathSciNet  Google Scholar 

  3. Bandelt, H.-J., Dress, A.: Reconstructing the shape of a tree from observed dissimilarity data. Adv. Appl. Math. 7, 309–343 (1986)

    Article  MATH  MathSciNet  Google Scholar 

  4. Baswana, S., Sen, S.: A simple linear time algorithm for computing (2k - 1)-spanner of O(n 1 + 1/k) size for weighted graphs. In: Proc. 30th ICALP, pp. 384–396

    Google Scholar 

  5. Cai, L.: NP-completeness of minimum spanner problems. Discr. Appl. Math. and Comb. Oper. Research and Comp. Sci. 48(2), 187–194 (1994)

    MATH  Google Scholar 

  6. Cai, L., Keil, J.M.: Degree-bounded spanners. Parallel Processing Letters 3, 457–468 (1993)

    Article  MathSciNet  Google Scholar 

  7. Chew, L.P.: There are planar graphs almost as good as the complete graph. Journal of Computer and System Sciences 39(2), 205–219 (1989)

    Article  MATH  MathSciNet  Google Scholar 

  8. Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to Algorithms. MIT Press, Cambridge (2001)

    MATH  Google Scholar 

  9. Das, G., Joseph, D.: Which triangulations approximate the complete graph. In: Proc. Int. Symp. on Optimal Algorithms, pp. 168–192

    Google Scholar 

  10. Dobkin, D., Friedman, S.J., Supowit, K.J.: Delaunay graphs are almost as good as complete graphs. Discrete Comput. Geom. 5, 399–407 (1990)

    Article  MATH  MathSciNet  Google Scholar 

  11. Liestman, A.L., Shermer, T.: Additive graph spanners. Networks 23, 343–364 (1993)

    Article  MATH  MathSciNet  Google Scholar 

  12. Liestman, A.L., Shermer, T.: Grid spanners. Networks 23, 122–133 (1993)

    Google Scholar 

  13. Peleg, D., Shäffer, A.: Graph spanners. J. of Graph Theory 13, 99–116 (1989)

    Article  MATH  Google Scholar 

  14. Peleg, D., Ullman, J.D.: An optimal synchronizer for the hypercube. SIAM Journal on Computing 18(4), 740–747 (1989)

    Article  MATH  MathSciNet  Google Scholar 

  15. Richards, D., Liestman, A.L.: Degree-constrained pyramid spanners. Journal of Parallel and Distributed Computing 25, 1–6 (1995)

    Article  Google Scholar 

  16. Roditty, L., Thorup, M., Zwick, U.: Deterministic constructions of approximate distance oracles and spanners. In: Caires, L., Italiano, G.F., Monteiro, L., Palamidessi, C., Yung, M. (eds.) ICALP 2005. LNCS, vol. 3580, pp. 261–272. Springer, Heidelberg (2005) (to appear)

    Chapter  Google Scholar 

  17. Roditty, L., Zwick, U.: Dynamic approximate all-pairs shortest paths in undirected graphs. In: Proc. FOCS 2004, pp. 499–508 (2004)

    Google Scholar 

  18. Roditty, L., Zwick, U.: On dynamic shortest paths problems. In: Albers, S., Radzik, T. (eds.) ESA 2004. LNCS, vol. 3221, pp. 580–591. Springer, Heidelberg (2004)

    Chapter  Google Scholar 

  19. Wenger, R.: Extremal graphs with no C 4’s, C 6’s, or C 10’s. J. Combin. Theory Ser. B 52, 113–116 (1991)

    Article  MATH  MathSciNet  Google Scholar 

  20. Zwick, U.: Personal communication

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Dipartimento di Informatica e Sistemistica, Università di Roma “La Sapienza”, Roma, Italy

    Giorgio Ausiello

  2. Dipartimento di Statistica, Probabilità e Statistiche Applicate, Università di Roma “La Sapienza”, Roma, Italy

    Paolo G. Franciosa

  3. Dipartimento di Informatica, Sistemi e Produzione, Università di Roma “Tor Vergata”, Roma, Italy

    Giuseppe F. Italiano

Authors
  1. Giorgio Ausiello
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Paolo G. Franciosa
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Giuseppe F. Italiano
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Editors and Affiliations

  1. BRICS, MADALGO, Department of Computer Science, University of Aarhus, Denmark

    Gerth Stølting Brodal

  2. University of Rome “La Sapienza”, Rome, Italy

    Stefano Leonardi

Rights and permissions

Reprints and permissions

Copyright information

© 2005 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Ausiello, G., Franciosa, P.G., Italiano, G.F. (2005). Small Stretch Spanners on Dynamic Graphs. In: Brodal, G.S., Leonardi, S. (eds) Algorithms – ESA 2005. ESA 2005. Lecture Notes in Computer Science, vol 3669. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11561071_48

Download citation

  • DOI: https://doi.org/10.1007/11561071_48

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-29118-3

  • Online ISBN: 978-3-540-31951-1

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics