{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,19]],"date-time":"2025-12-19T09:20:13Z","timestamp":1766136013057,"version":"3.37.0"},"reference-count":24,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2009,3,13]],"date-time":"2009-03-13T00:00:00Z","timestamp":1236902400000},"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":[[2010,11]]},"DOI":"10.1007\/s00453-009-9293-4","type":"journal-article","created":{"date-parts":[[2009,3,12]],"date-time":"2009-03-12T15:18:09Z","timestamp":1236871089000},"page":"711-729","source":"Crossref","is-referenced-by-count":21,"title":["Computing the Greedy Spanner in Near-Quadratic Time"],"prefix":"10.1007","volume":"58","author":[{"given":"Prosenjit","family":"Bose","sequence":"first","affiliation":[]},{"given":"Paz","family":"Carmi","sequence":"additional","affiliation":[]},{"given":"Mohammad","family":"Farshi","sequence":"additional","affiliation":[]},{"given":"Anil","family":"Maheshwari","sequence":"additional","affiliation":[]},{"given":"Michiel","family":"Smid","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2009,3,13]]},"reference":[{"issue":"1","key":"9293_CR1","doi-asserted-by":"crossref","first-page":"81","DOI":"10.1007\/BF02189308","volume":"9","author":"I. Alth\u00f6fer","year":"1993","unstructured":"Alth\u00f6fer, I., Das, G., Dobkin, D.P., Joseph, D., Soares, J.: On sparse spanners of weighted graphs. Discrete Comput. Geom. 9(1), 81\u2013100 (1993)","journal-title":"Discrete Comput. Geom."},{"key":"9293_CR2","doi-asserted-by":"crossref","first-page":"67","DOI":"10.1145\/200836.200853","volume":"42","author":"P.B. Callahan","year":"1995","unstructured":"Callahan, P.B., Kosaraju, S.R.: A decomposition of multidimensional point sets with applications to k-nearest-neighbors and n-body potential fields. J. ACM 42, 67\u201390 (1995)","journal-title":"J. ACM"},{"issue":"6","key":"9293_CR3","doi-asserted-by":"crossref","first-page":"289","DOI":"10.1016\/0020-0190(94)00104-9","volume":"51","author":"B. Chandra","year":"1994","unstructured":"Chandra, B.: Constructing sparse spanners for most graphs in higher dimensions. Inf. Process. Lett. 51(6), 289\u2013294 (1994)","journal-title":"Inf. Process. Lett."},{"key":"9293_CR4","doi-asserted-by":"crossref","first-page":"124","DOI":"10.1142\/S0218195995000088","volume":"5","author":"B. Chandra","year":"1995","unstructured":"Chandra, B., Das, G., Narasimhan, G., Soares, J.: New sparseness results on graph spanners. Int. J. Comput. Geom. Appl. 5, 124\u2013144 (1995)","journal-title":"Int. J. Comput. Geom. Appl."},{"key":"9293_CR5","doi-asserted-by":"crossref","unstructured":"Chew, L.P.: There is a planar graph almost as good as the complete graph. In: SCG\u201986: Proceedings of the 2nd Annual ACM Symposium on Computational Geometry, pp. 169\u2013177 (1986)","DOI":"10.1145\/10515.10534"},{"key":"9293_CR6","volume-title":"Introduction to Algorithms","author":"T.H. Cormen","year":"2001","unstructured":"Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to Algorithms, 2nd edn. MIT Press\/McGraw-Hill, Cambridge\/New York (2001)","edition":"2"},{"key":"9293_CR7","doi-asserted-by":"crossref","first-page":"297","DOI":"10.1142\/S0218195997000193","volume":"7","author":"G. Das","year":"1997","unstructured":"Das, G., Narasimhan, G.: A fast algorithm for constructing sparse Euclidean spanners. Int. J. Comput. Geom. Appl. 7, 297\u2013315 (1997)","journal-title":"Int. J. Comput. Geom. Appl."},{"key":"9293_CR8","doi-asserted-by":"crossref","unstructured":"Das, G., Heffernan, P.J., Narasimhan, G.: Optimally sparse spanners in 3-dimensional Euclidean space. In: SCG\u201993: Proceedings of the 9th Annual ACM Symposium on Computational Geometry, pp. 53\u201362 (1993)","DOI":"10.1145\/160985.160998"},{"key":"9293_CR9","doi-asserted-by":"crossref","first-page":"269","DOI":"10.1007\/BF01386390","volume":"1","author":"E.W. Dijkstra","year":"1959","unstructured":"Dijkstra, E.W.: A note on two problems in connexion with graphs. Numer. Math. 1, 269\u2013271 (1959)","journal-title":"Numer. Math."},{"key":"9293_CR10","doi-asserted-by":"crossref","first-page":"425","DOI":"10.1016\/B978-044482537-7\/50010-3","volume-title":"Handbook of Computational Geometry","author":"D. Eppstein","year":"2000","unstructured":"Eppstein, D.: Spanning trees and spanners. In: Sack, J.-R., Urrutia, J. (eds.) Handbook of Computational Geometry, pp. 425\u2013461. Elsevier, Amsterdam (2000)"},{"key":"9293_CR11","unstructured":"Farshi, M.: A theoretical and experimental study of geometric networks. Ph.D. Thesis, Department of Mathematics and Computer Science, Eindhoven University of Technology, Eindhoven, The Netherlands (2008)"},{"key":"9293_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"556","DOI":"10.1007\/11561071_50","volume-title":"ESA\u201905: Proceedings of the 13th Annual European Symposium on Algorithms","author":"M. Farshi","year":"2005","unstructured":"Farshi, M., Gudmundsson, J.: Experimental study of geometric t-spanners. In: ESA\u201905: Proceedings of the 13th Annual European Symposium on Algorithms. Lecture Notes in Computer Science, vol.\u00a03669, pp. 556\u2013567. Springer, Berlin (2005)"},{"key":"9293_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"270","DOI":"10.1007\/978-3-540-72845-0_21","volume-title":"WEA\u201907: Proceedings of the 6th Workshop on Experimental Algorithms","author":"M. Farshi","year":"2007","unstructured":"Farshi, M., Gudmundsson, J.: Experimental study of geometric t-spanners: A running time comparison. In: WEA\u201907: Proceedings of the 6th Workshop on Experimental Algorithms. Lecture Notes in Computer Science, vol. 4525, pp. 270\u2013284. Springer, Berlin (2007)"},{"key":"9293_CR14","volume-title":"Handbook on Approximation Algorithms and Metaheuristics","author":"J. Gudmundsson","year":"2007","unstructured":"Gudmundsson, J., Knauer, C.: Dilation and detour in geometric networks. In: Gonzalez, T. (ed.) Handbook on Approximation Algorithms and Metaheuristics. Chapman & Hall\/CRC Press, London\/Boca Raton (2007)"},{"issue":"5","key":"9293_CR15","doi-asserted-by":"crossref","first-page":"1479","DOI":"10.1137\/S0097539700382947","volume":"31","author":"J. Gudmundsson","year":"2002","unstructured":"Gudmundsson, J., Levcopoulos, C., Narasimhan, G.: Improved greedy algorithms for constructing sparse geometric spanners. SIAM J. Comput. 31(5), 1479\u20131500 (2002)","journal-title":"SIAM J. Comput."},{"key":"9293_CR16","unstructured":"Har-Peled, S.: A simple proof? http:\/\/valis.cs.uiuc.edu\/blog\/?p=441 (2006)"},{"issue":"5","key":"9293_CR17","doi-asserted-by":"crossref","first-page":"1148","DOI":"10.1137\/S0097539704446281","volume":"35","author":"S. Har-Peled","year":"2006","unstructured":"Har-Peled, S., Mendel, M.: Fast construction of nets in low-dimensional metrics and their applications. SIAM J. Comput. 35(5), 1148\u20131184 (2006)","journal-title":"SIAM J. Comput."},{"key":"9293_CR18","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511546884","volume-title":"Geometric Spanner Networks","author":"G. Narasimhan","year":"2007","unstructured":"Narasimhan, G., Smid, M.: Geometric Spanner Networks. Cambridge University Press, Cambridge (2007)"},{"key":"9293_CR19","doi-asserted-by":"crossref","DOI":"10.1137\/1.9780898719772","volume-title":"Distributed Computing: A Locality-Sensitive Approach","author":"D. Peleg","year":"2000","unstructured":"Peleg, D.: Distributed Computing: A Locality-Sensitive Approach. SIAM, Philadelphia (2000)"},{"key":"9293_CR20","doi-asserted-by":"crossref","first-page":"99","DOI":"10.1002\/jgt.3190130114","volume":"13","author":"D. Peleg","year":"1989","unstructured":"Peleg, D., Sch\u00e4ffer, A.: Graph spanners. J. Graph Theory 13, 99\u2013116 (1989)","journal-title":"J. Graph Theory"},{"key":"9293_CR21","doi-asserted-by":"crossref","unstructured":"Russel, D., Guibas, L.J.: Exploring protein folding trajectories using geometric spanners. In: Pacific Symposium on Biocomputing, pp. 40\u201351 (2005)","DOI":"10.1142\/9789812702456_0005"},{"key":"9293_CR22","doi-asserted-by":"crossref","first-page":"877","DOI":"10.1016\/B978-044482537-7\/50021-8","volume-title":"Handbook of Computational Geometry","author":"M. Smid","year":"2000","unstructured":"Smid, M.: Closest point problems in computational geometry. In: Sack, J.-R., Urrutia, J. (eds.) Handbook of Computational Geometry, pp. 877\u2013935. Elsevier, Amsterdam (2000)"},{"key":"9293_CR23","doi-asserted-by":"crossref","first-page":"213","DOI":"10.1007\/BF02574005","volume":"11","author":"J. Soares","year":"1994","unstructured":"Soares, J.: Approximating Euclidean distances by small degree graphs. Discrete Comput. Geom. 11, 213\u2013233 (1994)","journal-title":"Discrete Comput. Geom."},{"key":"9293_CR24","doi-asserted-by":"crossref","first-page":"281","DOI":"10.1145\/1007352.1007399","volume-title":"STOC\u201904: Proceedings of the 36th Annual ACM Symposium on Theory of Computing","author":"K. Talwar","year":"2004","unstructured":"Talwar, K.: Bypassing the embedding: algorithms for low dimensional metrics. In: STOC\u201904: Proceedings of the 36th Annual ACM Symposium on Theory of Computing, pp. 281\u2013290. ACM, New York (2004)"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-009-9293-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-009-9293-4\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-009-9293-4","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,2,8]],"date-time":"2025-02-08T10:23:40Z","timestamp":1739010220000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-009-9293-4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,3,13]]},"references-count":24,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2010,11]]}},"alternative-id":["9293"],"URL":"https:\/\/doi.org\/10.1007\/s00453-009-9293-4","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2009,3,13]]}}}