[go: up one dir, main page]
More Web Proxy on the site http://driver.im/
Skip to main content

Construction of Minimum-Weight Spanners

  • Conference paper
Algorithms – ESA 2004 (ESA 2004)

Part of the book series: Lecture Notes in Computer Science ((LNCS,volume 3221))

Included in the following conference series:

Abstract

Spanners are sparse subgraphs that preserve distances up to a given factor in the underlying graph. Recently spanners have found important practical applications in metric space searching and message distribution in networks. These applications use some variant of the so-called greedy algorithm for constructing the spanner — an algorithm that mimics Kruskal’s minimum spanning tree algorithm. Greedy spanners have nice theoretical properties, but their practical performance with respect to total weight is unknown. In this paper we give an exact algorithm for constructing minimum-weight spanners in arbitrary graphs. By using the solutions (and lower bounds) from this algorithm, we experimentally evaluate the performance of the greedy algorithm for a set of realistic problem instances.

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

Access this chapter

Subscribe and save

Springer+ Basic
£29.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
GBP 19.95
Price includes VAT (United Kingdom)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
GBP 71.50
Price includes VAT (United Kingdom)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
GBP 89.99
Price includes VAT (United Kingdom)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

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. Althöfer, I., Das, G., Dobkin, D., Joseph, D., Soares, J.: On Sparse Spanners of Weighted Graphs. Discrete and Computational Geometry 9, 81–100 (1993)

    Article  MATH  MathSciNet  Google Scholar 

  2. Aneja, Y.P., Aggarwal, V., Nair, K.P.K.: Shortest Chain Subject to Side Constraints. Networks 13, 295–302 (1983)

    Article  MathSciNet  Google Scholar 

  3. Cai, L.: NP-Completeness of Minimum Spanner Problem. Discrete Applied Mathematics 48, 187–194 (1994)

    Article  MATH  MathSciNet  Google Scholar 

  4. Chandra, B.: Constructing Sparse Spanners for Most Graphs in Higher Dimension. Information Processing Letters 51, 289–294 (1994)

    Article  MATH  MathSciNet  Google Scholar 

  5. Chandra, B., Das, G., Narasimhan, G., Soares, J.: New Sparseness Results on Graph Spanners. International Journal of Computational Geometry and Applications 5, 125–144 (1995)

    Article  MATH  MathSciNet  Google Scholar 

  6. Das, G., Narasimhan, G.: A Fast Algorithm for Constructing Sparse Euclidean Spanners. Int. J. Comput. Geometry Appl. 7(4), 297–315 (1997)

    Article  MATH  MathSciNet  Google Scholar 

  7. Das, G., Narasimhan, G., Salowe, J.S.: A New Way to Weigh Malnourished Euclidean Graphs. In: Proceedings of the 6th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 215–222 (1995)

    Google Scholar 

  8. Desrochers, M., Soumis, F.: A GeneralizedP ermanent Labelling Algorithm for the Shortest Path Problem with Time Windows. INFOR 26, 191–211 (1988)

    MATH  Google Scholar 

  9. Dodis, Y., Khanna, S.: Design Networks with Bounded Pairwise Distance. In: Proceedings of the 31th Annual ACM Symposium on Theory of Computing, pp. 750–759 (1999)

    Google Scholar 

  10. Eppstein, D.: Spanning Trees andSpanners. In: Handbook of Computational Geometry, pp. 425–461 (1999)

    Google Scholar 

  11. Farley, A.M., Zappala, D., Proskurowski, A., Windisch, K.: Spanners and Message Distribution in Networks. Discrete Applied Mathematics 137, 159–171 (2004)

    Article  MATH  MathSciNet  Google Scholar 

  12. Garey, M.R., Johnson, D.S.: Computers and Intractability. W.H.Freeman and Co., San Francisco (1979)

    MATH  Google Scholar 

  13. Gudmundsson, J., Levcopoulos, C., Narasimhan, G.: Fast Greedy Algorithms for Constructing Sparse Geometric Spanners. SIAM Journal on Computing 31(5), 1479–1500 (2002)

    Article  MATH  MathSciNet  Google Scholar 

  14. Gudmundsson, J., Levcopoulos, C., Narasimhan, G., Smid, M.: Approximate Distance Oracles for Geometric Graphs. In: Proceedings of the 13th Annual ACMSIAM Symposium on Discrete Algorithms, pp. 828–837 (2002)

    Google Scholar 

  15. Handler, G.Y., Zang, I.: A Dual Algorithm for the ConstrainedShortest Path Problem. Networks 10, 293–310 (1980)

    Article  MathSciNet  Google Scholar 

  16. ILOG. ILOG CPLEX 7.0, Reference Manual. ILOG, S.A., France (2000)

    Google Scholar 

  17. Joksch, H.C.: The Shortest Route Problem with Constraints. J. Math. Anal. Appl. 14, 191–197 (1966)

    Article  MATH  MathSciNet  Google Scholar 

  18. Khuller, S., Raghavachari, B., Young, N.: Balancing Minimum Spanning and Shortest-Path Trees. Algorithmica 14(4), 305–321 (1995)

    Article  MATH  MathSciNet  Google Scholar 

  19. Narasimhan, G., Zachariasen, M.: Geometric Minimum Spanning Trees via Well-Separated Pair Decompositions. ACM Journal of Experimental Algorithmics 6 (2001)

    Google Scholar 

  20. Navarro, G., Paredes, R.: Practical Construction of Metric t-Spanners. In: Proceedings of the 5th Workshop on Algorithm Engineering and Experiments, ALENEX 2003 (2003)

    Google Scholar 

  21. Navarro, G., Paredes, R., Chávez, E.: t-spanners as a data structure for metric space searching. In: Laender, A.H.F., Oliveira, A.L. (eds.) SPIRE 2002. LNCS, vol. 2476, pp. 298–309. Springer, Heidelberg (2002)

    Chapter  Google Scholar 

  22. Peleg, D., Schaffer, A.: Graph Spanners. Journal of Graph Theory 13(1), 99–116 (1989)

    Article  MATH  MathSciNet  Google Scholar 

  23. Rao, S.B., Smith, W.D.: Improved Approximation Schemes for Geometrical Graphs via ”Spanners” and ”Ban yans”. In: Proceedings 30th Annual ACM Symposium on Theory of Computing, pp. 540–550 (1998)

    Google Scholar 

  24. Sigurd, M., Ryan, D.: Stabilized Column Generation for Set Partitioning Optimization (in preparation) (2003)

    Google Scholar 

  25. Thienel, S.: ABACUS — A Branch-And-CUt System. PhD thesis, Universität zu Köln, Germany (1995)

    Google Scholar 

  26. Warburton, A.: Approximation of Pareto Optima in Multiple–Objective, Shortest Path Problems. Operations Research 35, 70–79 (1987)

    Article  MATH  MathSciNet  Google Scholar 

  27. Waxman, B.M.: Routing of Multipoint Connections. IEEE Journal on Selected Areas in Communications 6(9), 1617–1622 (1988)

    Article  Google Scholar 

  28. Ziegelmann, M.: Constrained Shortest Paths and Related Problems. PhD thesis, Universität des Saarlandes, Saarbrücken, Germany (2001)

    Google Scholar 

Download references

Author information

Authors and Affiliations

Authors

Editor information

Editors and Affiliations

Rights and permissions

Reprints and permissions

Copyright information

© 2004 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Sigurd, M., Zachariasen, M. (2004). Construction of Minimum-Weight Spanners. In: Albers, S., Radzik, T. (eds) Algorithms – ESA 2004. ESA 2004. Lecture Notes in Computer Science, vol 3221. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-30140-0_70

Download citation

  • DOI: https://doi.org/10.1007/978-3-540-30140-0_70

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-23025-0

  • Online ISBN: 978-3-540-30140-0

  • eBook Packages: Springer Book Archive

Publish with us

Policies and ethics