Article

Free access

Balancing minimum spanning and shortest path trees

Authors:

Samir Khuller,

Balaji Raghavachari,

Neal YoungAuthors Info & Claims

SODA '93: Proceedings of the fourth annual ACM-SIAM symposium on Discrete algorithms

Pages 243 - 250

Published: 01 January 1993 Publication History

PDF eReader

References

[1]

I. Alth6fer, G. Das, D. Dobkin, D. Joseph, Generating sparse spanners for weighted graphs, Proc. of 2nd Scandinavian Workshop on Algorithm Theory (SWAT), pp. 26-37, (1990).

Digital Library

Google Scholar

[2]

B. Awerbuch, A. Baratz, and D. Peleg, Costsensitive analysis of communication protocols, Proc. of 9th Symp. on Principles of Distributed Computing (PODC), pp. 177-187, (1990).

Digital Library

Google Scholar

[3]

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

Google Scholar

[4]

B. Chandra, G. Das, G. Narasimhan and J. Soares, New sparseness results on graph spanners, Proc. of 8th Symp. on Computational Geometry, (CG), pp. 192-201, (1992).

Digital Library

Google Scholar

[5]

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

Digital Library

Google Scholar

[6]

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

Google Scholar

[7]

T. H. Cormen, C. E. Leiserson, and R. L. Rivest, Introduction to Algorithms, The MiT Press, (1989)

Digital Library

Google Scholar

[8]

E.W. Dijkstra, A Note on Two Problems in Connexion with Graphs, Numerische Mathematik, 1, pp. 269-271 (1959).

Google Scholar

[9]

M. L. Fredma. n and R. E. Tarjan, Fibonacci heaps and their uses in improved network optimization algorithms, Journal of the A CM, 34 (3), pp. 596- 615,(1987).

Digital Library

Google Scholar

[10]

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), pp. 109-122, (1986).

Digital Library

Google Scholar

[11]

j. J~iJa, Introduction to Parallel Algorithms, Addison-Wesley, Reading, MA, (1991).

Digital Library

Google Scholar

[12]

J. B. Kruskal, On the Shortest Spanning Subtree of a Graph and the Traveling Salesman Problem, Proc. Amer. Math. Soc., 7, pp. 48-50 (1956).

Google Scholar

[13]

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

Digital Library

Google Scholar

[14]

F. P. Preparata and M. I. Shamos, Computational Geometry, Springer Verlag, (1985).

Digital Library

Google Scholar

[15]

R. C. Prim, Shortest Connection Networks and Some Generalizations, Bell System Tech. j., 36, pp. 1389-1401 (1957).

Google Scholar

Cited By

View all

Han KKahng AMoyes CZelikovsky AHu S(2018)A study of optimal cost-skew tradeoff and remaining suboptimality in interconnect tree constructionsProceedings of the 20th System Level Interconnect Prediction Workshop10.1145/3225209.3225215(1-8)Online publication date: 23-Jun-2018
https://dl.acm.org/doi/10.1145/3225209.3225215
Alpert CChow WHan KKahng ALi ZLiu DVenkatesh SChu CBustany I(2018)Prim-Dijkstra RevisitedProceedings of the 2018 International Symposium on Physical Design10.1145/3177540.3178239(10-17)Online publication date: 25-Mar-2018
https://dl.acm.org/doi/10.1145/3177540.3178239
Scheifele R(2017)Steiner Trees with Bounded RC-DelayAlgorithmica10.1007/s00453-016-0149-478:1(86-109)Online publication date: 1-May-2017
https://dl.acm.org/doi/10.1007/s00453-016-0149-4
Show More Cited By

Index Terms

Balancing minimum spanning and shortest path trees

Recommendations

Balancing minimum spanning trees and shortest-path trees

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 ...
Balancing minimum spanning trees and multiple-source minimum routing cost spanning trees on metric graphs

Both the building cost and the multiple-source routing cost are important considerations in construction of a network system. A spanning tree with minimum building cost among all spanning trees is called a minimum spanning tree (MST), and a spanning ...
Delay-Constrained Minimum Shortest Path Trees and Related Problems
Combinatorial Optimization and Applications
Abstract
Motivated by applications in communication networks of the diameter-constrained minimum spanning tree problem, we consider the delay-constrained minimum shortest path tree (DcMSPT) problem. Specifically, given a weighted graph $G = (V, E; w, c)$ and a ... $_{}$ $^{}$ $^{}$ $_{}$ $_{}$
$^{}$ $^{}$

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

SODA '93: Proceedings of the fourth annual ACM-SIAM symposium on Discrete algorithms

January 1993

506 pages

ISBN:0898713137

Chairman:
Vijaya Ramachandran

Publisher

Society for Industrial and Applied Mathematics

United States

Publication History

Published: 01 January 1993

Check for updates

Qualifiers

Article

Conference

SODA93

Sponsor:

SIGACT
SIAM

SODA93: Conference on Discrete Algorithms

January 25 - 27, 1993

Texas, Austin, USA

Acceptance Rates

Overall Acceptance Rate 411 of 1,322 submissions, 31%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

23
Total Citations
View Citations
752
Total Downloads

Downloads (Last 12 months)22
Downloads (Last 6 weeks)6

Reflects downloads up to 03 Oct 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Han KKahng AMoyes CZelikovsky AHu S(2018)A study of optimal cost-skew tradeoff and remaining suboptimality in interconnect tree constructionsProceedings of the 20th System Level Interconnect Prediction Workshop10.1145/3225209.3225215(1-8)Online publication date: 23-Jun-2018
https://dl.acm.org/doi/10.1145/3225209.3225215
Alpert CChow WHan KKahng ALi ZLiu DVenkatesh SChu CBustany I(2018)Prim-Dijkstra RevisitedProceedings of the 2018 International Symposium on Physical Design10.1145/3177540.3178239(10-17)Online publication date: 25-Mar-2018
https://dl.acm.org/doi/10.1145/3177540.3178239
Scheifele R(2017)Steiner Trees with Bounded RC-DelayAlgorithmica10.1007/s00453-016-0149-478:1(86-109)Online publication date: 1-May-2017
https://dl.acm.org/doi/10.1007/s00453-016-0149-4
Bartal YFiltser ANeiman O(2016)On notions of distortion and an almost minimum spanning tree with constant average distortionProceedings of the twenty-seventh annual ACM-SIAM symposium on Discrete algorithms10.5555/2884435.2884497(873-882)Online publication date: 10-Jan-2016
https://dl.acm.org/doi/10.5555/2884435.2884497
Huang JLi XYing YSun YDuan QXing CLu CNadimi EKim SWang W(2014)FAMOUSProceedings of the 2014 Conference on Research in Adaptive and Convergent Systems10.1145/2663761.2663763(149-154)Online publication date: 5-Oct-2014
https://dl.acm.org/doi/10.1145/2663761.2663763
Solomon SCheng SDevillers O(2014)Euclidean Steiner Shallow-Light TreesProceedings of the thirtieth annual symposium on Computational geometry10.1145/2582112.2582160(454-463)Online publication date: 8-Jun-2014
https://dl.acm.org/doi/10.1145/2582112.2582160
Shan FLiang WLuo JShen X(2013)Network lifetime maximization for time-sensitive data gathering in wireless sensor networksComputer Networks: The International Journal of Computer and Telecommunications Networking10.5555/2459506.245960857:5(1063-1077)Online publication date: 1-Apr-2013
https://dl.acm.org/doi/10.5555/2459506.2459608
Dinitz YElkin MSolomon S(2010)Low-Light Trees, and Tight Lower Bounds for Euclidean SpannersDiscrete & Computational Geometry10.5555/3116254.311632343:4(736-783)Online publication date: 1-Jun-2010
https://dl.acm.org/doi/10.5555/3116254.3116323
Shpungin HSegal M(2010)Near-optimal multicriteria spanner constructions in wireless ad hoc networksIEEE/ACM Transactions on Networking10.1109/TNET.2010.205338118:6(1963-1976)Online publication date: 1-Dec-2010
https://dl.acm.org/doi/10.1109/TNET.2010.2053381
Peleg D(2009)As Good as It GetsProceedings of the 11th International Symposium on Stabilization, Safety, and Security of Distributed Systems10.1007/978-3-642-05118-0_3(35-46)Online publication date: 5-Nov-2009
https://dl.acm.org/doi/10.1007/978-3-642-05118-0_3
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Index Terms

Recommendations

Balancing minimum spanning trees and shortest-path trees

Balancing minimum spanning trees and multiple-source minimum routing cost spanning trees on metric graphs

Delay-Constrained Minimum Shortest Path Trees and Related Problems