{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,19]],"date-time":"2025-03-19T11:15:52Z","timestamp":1742382952387},"publisher-location":"Berlin, Heidelberg","reference-count":17,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540584346"},{"type":"electronic","value":"9783540487944"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1994]]},"DOI":"10.1007\/bfb0049396","type":"book-chapter","created":{"date-parts":[[2006,3,6]],"date-time":"2006-03-06T18:42:35Z","timestamp":1141670555000},"page":"48-59","source":"Crossref","is-referenced-by-count":7,"title":["Efficient construction of a bounded degree spanner with low weight"],"prefix":"10.1007","author":[{"given":"Sunil","family":"Arya","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Michiel","family":"Smid","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2006,2,23]]},"reference":[{"key":"6_CR1","doi-asserted-by":"crossref","unstructured":"B. Chandra, G. Das, G. Narasimhan and J. Soares. New sparseness results on graph spanners. Proc. 8th ACM Sympos. Comput. Geom., 1992, pp. 192\u2013201.","DOI":"10.1145\/142675.142717"},{"key":"6_CR2","first-page":"11","volume-title":"Lecture Notes in Computer Science, Vol. 762","author":"G. Das","year":"1993","unstructured":"G. Das and P.J. Heffernan. Constructing degree-3 spanners with other sparseness properties. Proc. 4th Annual Intern. Symp. on Algorithms, Lecture Notes in Computer Science, Vol. 762, Springer-Verlag, Berlin, 1993, pp. 11\u201320."},{"key":"6_CR3","doi-asserted-by":"crossref","unstructured":"G. Das, P. Heffernan and G. Narasimhan. Optimally sparse spanners in 3-dimensional Euclidean space. Proc. 9th Annu. ACM Sympos. Comput. Geom., 1993, pp. 53\u201362.","DOI":"10.1145\/160985.160998"},{"key":"6_CR4","doi-asserted-by":"crossref","unstructured":"G. Das and G. Narasimhan. A fast algorithm for constructing sparse Euclidean spanners. Proc. 10th Annu. ACM Sympos. Comput. Geom., 1994.","DOI":"10.1145\/177424.177579"},{"key":"6_CR5","unstructured":"G. Das, G. Narasimhan and J. Salowe. Properties of Steiner minimum trees with applications to small weight Euclidean graphs. Manuscript, 1994."},{"key":"6_CR6","first-page":"265","volume-title":"Lecture Notes in Computer Science, Vol. 709","author":"A. Datta","year":"1993","unstructured":"A. Datta, H.P. Lenhof, C. Schwarz and M. Smid. Static and dynamic algorithms for k-point clustering problems. Proc. 3rd WADS, Lecture Notes in Computer Science, Vol. 709, Springer-Verlag, Berlin, 1993, pp. 265\u2013276."},{"key":"6_CR7","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 finding k nearest neighbors. Internat. J. Comput. Geom. Appl. 2 (1992), pp. 221\u2013239.","journal-title":"Internat. J. Comput. Geom. Appl."},{"key":"6_CR8","doi-asserted-by":"crossref","unstructured":"H.-P. Lenhof and M. Smid. Enumerating the k closest pairs optimally. Proc. 33rd Annu. IEEE Sympos. Found. Comput. Sci., 1992, pp. 380\u2013386.","DOI":"10.1109\/SFCS.1992.267752"},{"key":"6_CR9","doi-asserted-by":"publisher","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), pp. 215\u2013241.","journal-title":"Algorithmica"},{"key":"6_CR10","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":"6_CR11","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), pp. 99\u2013107.","journal-title":"Internat. J. Comput. Geom. Appl."},{"key":"6_CR12","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), pp. 49\u201359.","journal-title":"Internat. J. Comput. Geom. Appl."},{"key":"6_CR13","doi-asserted-by":"crossref","unstructured":"J.S. Salowe. On Euclidean spanner graphs with small degree. Proc. 8th Annu. ACM Sympos. Comput. Geom., 1992, pp. 186\u2013191.","DOI":"10.1145\/142675.142716"},{"key":"6_CR14","unstructured":"J.S. Salowe. Personal communication, 1994."},{"key":"6_CR15","doi-asserted-by":"publisher","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), pp. 415\u2013431.","journal-title":"Discrete Comput. Geom."},{"key":"6_CR16","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 in K dimensions. Discrete Comput. Geom. 6 (1991), pp. 369\u2013381.","journal-title":"Discrete Comput. Geom."},{"key":"6_CR17","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 in k-dimensional spaces and related problems. SLAM J. Comput. 11 (1982), pp. 721\u2013736.","journal-title":"SLAM J. Comput."}],"container-title":["Lecture Notes in Computer Science","Algorithms \u2014 ESA '94"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BFb0049396","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,4,17]],"date-time":"2019-04-17T05:56:30Z","timestamp":1555480590000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BFb0049396"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1994]]},"ISBN":["9783540584346","9783540487944"],"references-count":17,"URL":"https:\/\/doi.org\/10.1007\/bfb0049396","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1994]]}}}