{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,1]],"date-time":"2026-01-01T03:56:24Z","timestamp":1767239784293,"version":"3.40.3"},"publisher-location":"Berlin, Heidelberg","reference-count":13,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540699002"},{"type":"electronic","value":"9783540699033"}],"license":[{"start":{"date-parts":[[2008,1,1]],"date-time":"2008-01-01T00:00:00Z","timestamp":1199145600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2008,1,1]],"date-time":"2008-01-01T00:00:00Z","timestamp":1199145600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2008]]},"DOI":"10.1007\/978-3-540-69903-3_35","type":"book-chapter","created":{"date-parts":[[2008,8,12]],"date-time":"2008-08-12T16:07:43Z","timestamp":1218557263000},"page":"390-401","source":"Crossref","is-referenced-by-count":3,"title":["Computing the Greedy Spanner in Near-Quadratic Time"],"prefix":"10.1007","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","reference":[{"issue":"1","key":"35_CR1","doi-asserted-by":"publisher","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 and Computational Geometry\u00a09(1), 81\u2013100 (1993)","journal-title":"Discrete and Computational Geometry"},{"key":"35_CR2","doi-asserted-by":"publisher","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. Journal of the ACM\u00a042, 67\u201390 (1995)","journal-title":"Journal of the ACM"},{"doi-asserted-by":"crossref","unstructured":"Chew, L.P.: There is a planar graph almost as good as the complete graph. In: SCG 1986: Proceedings of the 2nd Annual ACM Symposium on Computational Geometry, pp. 169\u2013177 (1986)","key":"35_CR3","DOI":"10.1145\/10515.10534"},{"key":"35_CR4","doi-asserted-by":"publisher","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. of Computational Geometry & Applications\u00a07, 297\u2013315 (1997)","journal-title":"Int. J. of Computational Geometry & Applications"},{"key":"35_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"556","DOI":"10.1007\/11561071_50","volume-title":"Algorithms \u2013 ESA 2005","author":"M. Farshi","year":"2005","unstructured":"Farshi, M., Gudmundsson, J.: Experimental study of geometric t-spanners. In: Brodal, G.S., Leonardi, S. (eds.) ESA 2005. LNCS, vol.\u00a03669, pp. 556\u2013567. Springer, Heidelberg (2005)"},{"key":"35_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"270","DOI":"10.1007\/978-3-540-72845-0_21","volume-title":"Experimental Algorithms","author":"M. Farshi","year":"2007","unstructured":"Farshi, M., Gudmundsson, J.: Experimental study of geometric t-spanners: A running time comparison. In: Demetrescu, C. (ed.) WEA 2007. LNCS, vol.\u00a04525, pp. 270\u2013284. Springer, Heidelberg (2007)"},{"unstructured":"Har-Peled, S.: A simple proof? (2006), http:\/\/valis.cs.uiuc.edu\/blog\/?p=362","key":"35_CR7"},{"issue":"5","key":"35_CR8","doi-asserted-by":"publisher","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 Journal on Computing\u00a035(5), 1148\u20131184 (2006)","journal-title":"SIAM Journal on Computing"},{"key":"35_CR9","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1007\/BF02187821","volume":"7","author":"J.M. Keil","year":"1992","unstructured":"Keil, J.M., Gutwin, C.A.: Classes of graphs which approximate the complete Euclidean graph. Discrete and Computational Geometry\u00a07, 13\u201328 (1992)","journal-title":"Discrete and Computational Geometry"},{"key":"35_CR10","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":"35_CR11","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":"35_CR12","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1002\/jgt.3190130114","volume":"13","author":"D. Peleg","year":"1989","unstructured":"Peleg, D., Sch\u00e4ffer, A.: Graph spanners. Journal of Graph Theory\u00a013, 99\u2013116 (1989)","journal-title":"Journal of Graph Theory"},{"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)","key":"35_CR13","DOI":"10.1142\/9789812702456_0005"}],"container-title":["Lecture Notes in Computer Science","Algorithm Theory \u2013 SWAT 2008"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-69903-3_35","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,31]],"date-time":"2025-01-31T12:09:09Z","timestamp":1738325349000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-540-69903-3_35"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008]]},"ISBN":["9783540699002","9783540699033"],"references-count":13,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-69903-3_35","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2008]]}}}