{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,3]],"date-time":"2025-10-03T18:04:26Z","timestamp":1759514666678},"reference-count":18,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[1997,1,1]],"date-time":"1997-01-01T00:00:00Z","timestamp":852076800000},"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":[[1997,1]]},"DOI":"10.1007\/bf02523237","type":"journal-article","created":{"date-parts":[[2006,11,8]],"date-time":"2006-11-08T04:39:46Z","timestamp":1162960786000},"page":"33-54","source":"Crossref","is-referenced-by-count":37,"title":["Efficient construction of a bounded-degree spanner with low weight"],"prefix":"10.1007","volume":"17","author":[{"given":"S.","family":"Arya","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"M.","family":"Smid","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"BF02523237_CR1","doi-asserted-by":"crossref","unstructured":"S. Arya, G. Das, D. M. Mount, J. S. Salowe, and M. Smid. Euclidean spanners: short, thin, and lanky.Proc. 27th Annual ACM Symp. on the Theory of Computing, 1995, pp. 489\u2013498.","DOI":"10.1145\/225058.225191"},{"key":"BF02523237_CR2","doi-asserted-by":"crossref","unstructured":"B. Chandra, G. Das, G. Narasimhan, and J. Soares. New sparseness results on graph spanners.Proc. 8th Annual ACM Symp. on Computational Geometry, 1992, pp. 192\u2013201.","DOI":"10.1145\/142675.142717"},{"key":"BF02523237_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"11","DOI":"10.1007\/3-540-57568-5_230","volume-title":"Constructing degree-3 spanners with other sparseness properties","author":"G. Das","year":"1993","unstructured":"G. Das and P. J. Heffernan, Constructing degree-3 spanners with other sparseness properties.Proc. 4th Annual Internat. Symp. on Algorithms, 1993, pp. 11\u201320. Lecture Notes in Computer Science, Vol. 762, Springer-Verlag, Berlin."},{"key":"BF02523237_CR4","doi-asserted-by":"crossref","unstructured":"G. Das, P. Heffernan, and G. Narasimhan. Optimally sparse spanners in three-dimensional Euclidean space.Proc. 9th Annual ACM Symp. on Computational Geometry, 1993, pp. 53\u201362.","DOI":"10.1145\/160985.160998"},{"key":"BF02523237_CR5","doi-asserted-by":"crossref","unstructured":"G. Das and G. Narasimhan. A fast algorithm for constructing sparse Euclidean spanners.Proc. 10th Annual ACM Symp. on Computational Geometry, 1994, pp. 132\u2013139.","DOI":"10.1145\/177424.177579"},{"key":"BF02523237_CR6","unstructured":"G. Das, G. Narasimhan, and J. Salowe. A new way to weigh malnourished Euclidean graphs.Proc. 6th Annual ACM-SIAM Symp. on Discrete Algorithms, 1995, pp. 215\u2013222."},{"key":"BF02523237_CR7","series-title":"Proc. 3rd WADS","first-page":"265","volume-title":"Static and dynamic algorithms fork-point clustering problems","author":"A. Datta","year":"1993","unstructured":"A. Datta, H. P. Lenhof, C. Schwarz, and M. Smid. Static and dynamic algorithms fork-point clustering problems.Proc. 3rd WADS, 1993, pp. 265\u2013276. Lecture Notes in Computer Science, Vol. 709, Springer-Verlag, Berlin."},{"key":"BF02523237_CR8","doi-asserted-by":"crossref","first-page":"221","DOI":"10.1142\/S0218195992000147","volume":"2","author":"M. T. Dickerson","year":"1992","unstructured":"M. T. Dickerson, R. L. Drysdale, and J. R. Sack. Simple algorithms for enumerating interpoint distances and findingk nearest neighbors.Internat. J. Comput. Geom. Appl. 2 (1992), 221\u2013239.","journal-title":"Internat. J. Comput. Geom. Appl."},{"key":"BF02523237_CR9","doi-asserted-by":"crossref","unstructured":"H.-P. Lenhof and M. Smid. Enumerating thek closet pairs optimally.Proc. 33rd Annual IEEE Symp. on Foundations of Computer Science, 1992, pp. 380\u2013386.","DOI":"10.1109\/SFCS.1992.267752"},{"key":"BF02523237_CR10","doi-asserted-by":"crossref","first-page":"215","DOI":"10.1007\/BF01840386","volume":"5","author":"K. Mehlhorn","year":"1990","unstructured":"K. Mehlhorn and S. N\u00e4her. Dynamic fractional cascading.Algorithmica 5 (1990), 215\u2013241.","journal-title":"Algorithmica"},{"key":"BF02523237_CR11","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-1098-6","volume-title":"Computational Geometry, an Introduction","author":"F. P. Preparata","year":"1985","unstructured":"F. P. Preparata and M. I. Shamos,Computational Geometry, an Introduction. Springer-Verlag, New York, 1985."},{"key":"BF02523237_CR12","doi-asserted-by":"crossref","first-page":"99","DOI":"10.1142\/S0218195991000098","volume":"1","author":"J. S. Salowe","year":"1991","unstructured":"J. S. Salowe. Constructing multidimensional spanner graphs.Internat. J. Comput. Geom. Appl. 1 (1991), 99\u2013107.","journal-title":"Internat. J. Comput. Geom. Appl."},{"key":"BF02523237_CR13","doi-asserted-by":"crossref","first-page":"49","DOI":"10.1142\/S0218195992000044","volume":"2","author":"J. S. Salowe","year":"1992","unstructured":"J. S. Salowe. Enumerating interdistances in space.Internat. J. Comput. Geom. Appl. 2 (1992), 49\u201359.","journal-title":"Internat. J. Comput. Geom. Appl."},{"key":"BF02523237_CR14","doi-asserted-by":"crossref","unstructured":"J. S. Salowe. On Euclidean spanner graphs with small degree.Proc. 8th Annual ACM Symp. on Computational Geometry, 1992, pp. 186\u2013191.","DOI":"10.1145\/142675.142716"},{"key":"BF02523237_CR15","unstructured":"J. S. Salowe. Personal communication, 1994."},{"key":"BF02523237_CR16","doi-asserted-by":"crossref","first-page":"415","DOI":"10.1007\/BF02187852","volume":"7","author":"M. Smid","year":"1992","unstructured":"M. Smid. Maintaining the minimal distance of a point set in polylogarithmic time.Discrete Comput. Geom. 7 (1992), 415\u2013431.","journal-title":"Discrete Comput. Geom."},{"key":"BF02523237_CR17","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 Comput. Geom. 6 (1991), 369\u2013381.","journal-title":"Discrete Comput. Geom."},{"key":"BF02523237_CR18","doi-asserted-by":"crossref","first-page":"721","DOI":"10.1137\/0211059","volume":"11","author":"A. C. Yao","year":"1982","unstructured":"A. C. Yao. On constructing minimum spanning trees ink-dimensional spaces and related problems.SIAM J. Comput. 11 (1982), 721\u2013736.","journal-title":"SIAM J. Comput."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF02523237.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF02523237\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF02523237","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,19]],"date-time":"2019-05-19T20:39:41Z","timestamp":1558298381000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF02523237"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1997,1]]},"references-count":18,"journal-issue":{"issue":"1","published-print":{"date-parts":[[1997,1]]}},"alternative-id":["BF02523237"],"URL":"https:\/\/doi.org\/10.1007\/bf02523237","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[1997,1]]}}}