{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,1]],"date-time":"2026-01-01T03:56:23Z","timestamp":1767239783302,"version":"3.37.3"},"reference-count":13,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2015,4,20]],"date-time":"2015-04-20T00:00:00Z","timestamp":1429488000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2015,11]]},"DOI":"10.1007\/s00453-015-0001-2","type":"journal-article","created":{"date-parts":[[2015,4,19]],"date-time":"2015-04-19T03:26:06Z","timestamp":1429413966000},"page":"589-606","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":7,"title":["Computing the Greedy Spanner in Linear Space"],"prefix":"10.1007","volume":"73","author":[{"given":"Sander P. A.","family":"Alewijnse","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1101-0904","authenticated-orcid":false,"given":"Quirijn W.","family":"Bouts","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Alex P.","family":"ten Brink","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Kevin","family":"Buchin","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2015,4,20]]},"reference":[{"key":"1_CR1","doi-asserted-by":"crossref","unstructured":"Alewijnse, S.P., Bouts, Q.W., ten Brink, A.P.: Distribution-sensitive construction of the greedy spanner. In: 22nd Annual European Symposium on Algorithms (ESA), volume 8737 of Lecture Notes in Computer Science, pp. 61\u201373. Springer (2014)","DOI":"10.1007\/978-3-662-44777-2_6"},{"issue":"3","key":"1_CR2","doi-asserted-by":"crossref","first-page":"711","DOI":"10.1007\/s00453-009-9293-4","volume":"58","author":"P Bose","year":"2010","unstructured":"Bose, P., Carmi, P., Farshi, M., Maheshwari, A., Smid, M.: Computing the greedy spanner in near-quadratic time. Algorithmica 58(3), 711\u2013729 (2010)","journal-title":"Algorithmica"},{"key":"1_CR3","doi-asserted-by":"crossref","unstructured":"Bouts, Q.W., ten Brink, A.P., Buchin, K.: A framework for computing the greedy spanner. In: Proceedings of the Thirtieth Annual Symposium on Computational Geometry, SOCG \u201914, pp. 11\u201319. ACM (2014)","DOI":"10.1145\/2582112.2582154"},{"key":"1_CR4","unstructured":"Callahan, P.B.: Dealing with higher dimensions: the well-separated pair decomposition and its applications. PhD thesis, Johns Hopkins University, Baltimore, Maryland (1995)"},{"issue":"1","key":"1_CR5","doi-asserted-by":"crossref","first-page":"67","DOI":"10.1145\/200836.200853","volume":"42","author":"PB 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(1), 67\u201390 (1995)","journal-title":"J. ACM"},{"issue":"2","key":"1_CR6","doi-asserted-by":"crossref","first-page":"205","DOI":"10.1016\/0022-0000(89)90044-5","volume":"39","author":"LP Chew","year":"1989","unstructured":"Chew, L.P.: There are planar graphs almost as good as the complete graph. J. Compute. Syst. Sci. 39(2), 205\u2013219 (1989)","journal-title":"J. Compute. Syst. Sci."},{"key":"1_CR7","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1145\/1498698.1564499","volume":"14","author":"M Farshi","year":"2009","unstructured":"Farshi, M., Gudmundsson, J.: Experimental study of geometric t-spanners. ACM J. Exp. Algorithm. 14, 3 (2009)","journal-title":"ACM J. Exp. Algorithm."},{"issue":"1","key":"1_CR8","doi-asserted-by":"crossref","first-page":"174","DOI":"10.1109\/JSAC.2004.837364","volume":"23","author":"J Gao","year":"2005","unstructured":"Gao, J., Guibas, L.J., Hershberger, J., Zhang, L., Zhu, A.: Geometric spanners for routing in mobile networks. IEEE J. Sel. Areas Commun. 23(1), 174\u2013185 (2005)","journal-title":"IEEE J. Sel. Areas Commun."},{"key":"1_CR9","unstructured":"Goldberg, A.V., Harrelson, C.: Computing the shortest path: a search meets graph theory. In: 16th ACM-SIAM Symposium on Discrete Algorithms, pp. 156\u2013165. SIAM (2005)"},{"key":"1_CR10","first-page":"52\u20131","volume-title":"Handbook on Approximation Algorithms and Metaheuristics","author":"J Gudmundsson","year":"2006","unstructured":"Gudmundsson, J., Knauer, C.: Dilation and detours in geometric networks. In: Gonzales, T. (ed.) Handbook on Approximation Algorithms and Metaheuristics, pp. 52\u20131\u201352\u201316. Chapman & Hall\/CRC, Boca Raton (2006)"},{"key":"1_CR11","doi-asserted-by":"crossref","unstructured":"Keil, J.M.: Approximating the complete euclidean graph. In: 1st Scandinavian Workshop on Algorithm Theory (SWAT), volume 318 of LNCS, pp. 208\u2013213. Springer (1988)","DOI":"10.1007\/3-540-19487-8_23"},{"key":"1_CR12","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, New York (2007)"},{"issue":"1","key":"1_CR13","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.A.: Graph spanners. J. Graph Theory 13(1), 99\u2013116 (1989)","journal-title":"J. Graph Theory"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-015-0001-2\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-015-0001-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-015-0001-2","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,8,9]],"date-time":"2023-08-09T16:10:50Z","timestamp":1691597450000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-015-0001-2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,4,20]]},"references-count":13,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2015,11]]}},"alternative-id":["1"],"URL":"https:\/\/doi.org\/10.1007\/s00453-015-0001-2","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2015,4,20]]}}}