Skip to main content
SpringerLink
Log in

Balancing minimum spanning trees and shortest-path trees

  • Published:
Algorithmica Aims and scope Submit manuscript

Abstract

We give a simple algorithm to find a spanning tree that simultaneously approximates a shortest-path tree and a minimum spanning tree. The algorithm provides a continuous tradeoff: given the two trees and aγ>0, the algorithm returns a spanning tree in which the distance between any vertex and the root of the shortest-path tree is at most 1+√2γ times the shortest-path distance, and yet the total weight of the tree is at most 1+√2/γ times the weight of a minimum spanning tree. Our algorithm runs in linear time and obtains the best-possible tradeoff. It can be implemented on a CREW PRAM to run a logarithmic time using one processor per vertex.

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

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Similar content being viewed by others

References

  1. I. Althöfer, G. Das, D. Dobkin, D. Joseph, and J. Soares, On sparse spanners of weighted graphs,Discrete and Computational Geometry,9(1) (1993), 81–100.

    Google Scholar 

  2. B. Awerbuch, A. Baratz, and D. Peleg, Cost-sensitive anlaysis of communication protocols,Proc. 9th Symp. on Principles of Distributed Computing, 1990, pp. 177–187.

  3. B. Awerbuch, A. Baratz, and D. Peleg, Efficient broadcast and light-weight spanners, Manuscript (1991).

  4. K. Bharath-Kumar and J. M. Jaffe, Routing to multiple destinations in computer networks,IEEE Transactions on Communications,31(3) (1983), 343–351.

    Google Scholar 

  5. B. Chandra, G. Das, G. Narasimhan, and J. Soares, New sparseness results on graph spanners,Proc. 8th Symp. on Conputational Geometry, 1992, pp. 192–201.

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

    Google Scholar 

  7. J. Cong, A. B. Kahng, G. Robins, M. Sarrafzadeh, and C. K. Wong, Performance-driven global routing for cell based IC's,Proc. IEEE Internat. Conf. on Computer Design, 1991, pp. 170–173.

  8. J. Cong, A. B. Kahng, G. Robins, M. Sarrafzadeh, and C. K. Wong, Provably good performance-driven global routing,IEEE Transactions on CAD, (1992), 739–752.

  9. J. Cong, A. B. Kahng, G. Robins, M. Sarrafzadeh, and C. K. Wong, Provably good algorithms for performance-driven global routing,Proc. IEEE Internat. Symp. on Circuits and Systems, San Diego, 1992, pp. 2240–2243.

  10. T. H. Cormen, C. E. Leiserson, and R. L. Rivest,Introduction to Algorithms, MIT Press, Cambridge, MA, 1989.

    Google Scholar 

  11. E. W. Dijkstra, A note on two problems in connexion with graphs,Numerische Mathematik,1 (1959), 269–271.

    Google Scholar 

  12. M. L. Freeman and R. E. Tarjan, Fibonacci heaps and their uses in improved network optimization algorithms,Journal of the ACM,34(3) (1987), 596–615.

    Google Scholar 

  13. H. N. Gabow, Z. Galil, T. Spencer, and R. E. Tarjan, Efficient algorithms for finding minimum spanning trees in undirected and directed graphs,Combinatorica,6(2) (1986), 109–122.

    Google Scholar 

  14. J. JáJáIntroduction to Parallel Algorithms, Addison-Wesley, Reading, MA, 1991.

    Google Scholar 

  15. J. B. Kruskal, On the shortest spanning subtree of a graph and the traveling salesman problem,Proceedings of the American Mathematical Society,7, (1956), pp. 48–50.

    Google Scholar 

  16. C. Levcopoulos and A. Lingas, There are planar graphs almost as good as the complete graphs and almost as cheap as minimum spanning trees,Algorithmica,8(3) (1992), 251–256.

    Google Scholar 

  17. D. Peleg and J. D. Ullman, An optimal synchronizer for the hypercube,Proc. 6th Symp. on Principles of Distributed Computing, 1987, pp. 77–85.

  18. F. P. Preparata and M. I. Shamos,Computational Geometry, Springer-Verlag, New York, 1985.

    Google Scholar 

  19. R. C. Prim, Shortest connection networks and some generalizations,Bell System Technical Journal,36 (1957), 1389–1401.

    Google Scholar 

  20. P. M. Vaidya, A sparse graph almost as good as the complete graph on points inK dimensions,Discrete and Computational Geometry,6 (1991), 369–381.

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Computer Science and Institute for Advanced Computer Studies, University of Maryland, 20742, College Park, MD, USA

    S. Khuller

  2. Department of Computer Science, University of Texas at Dallas, Box 830688, 75083-0688, Richardson, TX, USA

    B. Raghavachari

  3. Department of Computer Science, Princeton University, 08544, Princeton, NJ, USA

    N. Young

Authors
  1. S. Khuller
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. B. Raghavachari
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. N. Young
    View author publications

    You can also search for this author in PubMed Google Scholar

Additional information

Communicated by T. Nishizeki.

Current research supported by NSF Research Initiation Award CCR-9307462. This work was done while this author was supported by NSF Grants CCR-8906949, CCR-9103135, and CCR-9111348.

Part of this work was done while this, author was at the University of Maryland Institute for Advanced Computer Studies (UMIACS) and supported by NSF Grants CCR-8906949 and CCR-9111348.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Khuller, S., Raghavachari, B. & Young, N. Balancing minimum spanning trees and shortest-path trees. Algorithmica 14, 305–321 (1995). https://doi.org/10.1007/BF01294129

Download citation

  • Received:

  • Revised:

  • Issue Date:

  • DOI: https://doi.org/10.1007/BF01294129

Key words

Search

Navigation