{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,28]],"date-time":"2026-01-28T23:30:54Z","timestamp":1769643054518,"version":"3.49.0"},"reference-count":20,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[1995,10,1]],"date-time":"1995-10-01T00:00:00Z","timestamp":812505600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[1995,10]]},"DOI":"10.1007\/bf01294129","type":"journal-article","created":{"date-parts":[[2005,3,25]],"date-time":"2005-03-25T03:39:08Z","timestamp":1111721948000},"page":"305-321","source":"Crossref","is-referenced-by-count":187,"title":["Balancing minimum spanning trees and shortest-path trees"],"prefix":"10.1007","volume":"14","author":[{"given":"S.","family":"Khuller","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"B.","family":"Raghavachari","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"N.","family":"Young","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"1","key":"CR1","doi-asserted-by":"crossref","first-page":"81","DOI":"10.1007\/BF02189308","volume":"9","author":"I. Alth\u00f6fer","year":"1993","unstructured":"I. Alth\u00f6fer, G. Das, D. Dobkin, D. Joseph, and J. Soares, On sparse spanners of weighted graphs,Discrete and Computational Geometry,9(1) (1993), 81?100.","journal-title":"Discrete and Computational Geometry"},{"key":"CR2","doi-asserted-by":"crossref","unstructured":"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.","DOI":"10.1145\/93385.93417"},{"key":"CR3","unstructured":"B. Awerbuch, A. Baratz, and D. Peleg, Efficient broadcast and light-weight spanners, Manuscript (1991)."},{"issue":"3","key":"CR4","doi-asserted-by":"crossref","first-page":"343","DOI":"10.1109\/TCOM.1983.1095818","volume":"31","author":"K. Bharath-Kumar","year":"1983","unstructured":"K. Bharath-Kumar and J. M. Jaffe, Routing to multiple destinations in computer networks,IEEE Transactions on Communications,31(3) (1983), 343?351.","journal-title":"IEEE Transactions on Communications"},{"key":"CR5","doi-asserted-by":"crossref","unstructured":"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.","DOI":"10.1145\/142675.142717"},{"issue":"2","key":"CR6","doi-asserted-by":"crossref","first-page":"205","DOI":"10.1016\/0022-0000(89)90044-5","volume":"39","author":"L. P. Chew","year":"1989","unstructured":"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.","journal-title":"Journal of Computer and System Sciences"},{"key":"CR7","doi-asserted-by":"crossref","unstructured":"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.","DOI":"10.1109\/ICCD.1991.139874"},{"key":"CR8","doi-asserted-by":"crossref","unstructured":"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.","DOI":"10.1109\/43.137519"},{"key":"CR9","doi-asserted-by":"crossref","unstructured":"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.","DOI":"10.1109\/ISCAS.1992.230514"},{"key":"CR10","volume-title":"Introduction to Algorithms","author":"T. H. Cormen","year":"1989","unstructured":"T. H. Cormen, C. E. Leiserson, and R. L. Rivest,Introduction to Algorithms, MIT Press, Cambridge, MA, 1989."},{"key":"CR11","doi-asserted-by":"crossref","first-page":"269","DOI":"10.1007\/BF01386390","volume":"1","author":"E. W. Dijkstra","year":"1959","unstructured":"E. W. Dijkstra, A note on two problems in connexion with graphs,Numerische Mathematik,1 (1959), 269?271.","journal-title":"Numerische Mathematik"},{"issue":"3","key":"CR12","doi-asserted-by":"crossref","first-page":"596","DOI":"10.1145\/28869.28874","volume":"34","author":"M. L. Freeman","year":"1987","unstructured":"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.","journal-title":"Journal of the ACM"},{"issue":"2","key":"CR13","doi-asserted-by":"crossref","first-page":"109","DOI":"10.1007\/BF02579168","volume":"6","author":"H. N. Gabow","year":"1986","unstructured":"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.","journal-title":"Combinatorica"},{"key":"CR14","volume-title":"Introduction to Parallel Algorithms","author":"J. J\u00e1J\u00e1","year":"1991","unstructured":"J. J\u00e1J\u00e1Introduction to Parallel Algorithms, Addison-Wesley, Reading, MA, 1991."},{"key":"CR15","doi-asserted-by":"crossref","first-page":"48","DOI":"10.1090\/S0002-9939-1956-0078686-7","volume":"7","author":"J. B. Kruskal","year":"1956","unstructured":"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.","journal-title":"Proceedings of the American Mathematical Society"},{"issue":"3","key":"CR16","doi-asserted-by":"crossref","first-page":"251","DOI":"10.1007\/BF01758846","volume":"8","author":"C. Levcopoulos","year":"1992","unstructured":"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.","journal-title":"Algorithmica"},{"key":"CR17","doi-asserted-by":"crossref","unstructured":"D. Peleg and J. D. Ullman, An optimal synchronizer for the hypercube,Proc. 6th Symp. on Principles of Distributed Computing, 1987, pp. 77?85.","DOI":"10.1145\/41840.41847"},{"key":"CR18","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-1098-6","volume-title":"Computational Geometry","author":"F. P. Preparata","year":"1985","unstructured":"F. P. Preparata and M. I. Shamos,Computational Geometry, Springer-Verlag, New York, 1985."},{"key":"CR19","doi-asserted-by":"crossref","first-page":"1389","DOI":"10.1002\/j.1538-7305.1957.tb01515.x","volume":"36","author":"R. C. Prim","year":"1957","unstructured":"R. C. Prim, Shortest connection networks and some generalizations,Bell System Technical Journal,36 (1957), 1389?1401.","journal-title":"Bell System Technical Journal"},{"key":"CR20","doi-asserted-by":"crossref","first-page":"369","DOI":"10.1007\/BF02574695","volume":"6","author":"P. M. Vaidya","year":"1991","unstructured":"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.","journal-title":"Discrete and Computational Geometry"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01294129.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF01294129\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01294129","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,12,28]],"date-time":"2024-12-28T19:41:59Z","timestamp":1735414919000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF01294129"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1995,10]]},"references-count":20,"journal-issue":{"issue":"4","published-print":{"date-parts":[[1995,10]]}},"alternative-id":["BF01294129"],"URL":"https:\/\/doi.org\/10.1007\/bf01294129","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[1995,10]]}}}