{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,27]],"date-time":"2025-03-27T08:16:00Z","timestamp":1743063360423,"version":"3.40.3"},"publisher-location":"Boston, MA","reference-count":20,"publisher":"Springer US","isbn-type":[{"type":"print","value":"9780387307701"},{"type":"electronic","value":"9780387301624"}],"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.springer.com\/tdm"},{"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.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2008]]},"DOI":"10.1007\/978-0-387-30162-4_167","type":"book-chapter","created":{"date-parts":[[2008,6,26]],"date-time":"2008-06-26T18:38:09Z","timestamp":1214505489000},"page":"360-364","source":"Crossref","is-referenced-by-count":4,"title":["Geometric Spanners"],"prefix":"10.1007","author":[{"given":"Joachim","family":"Gudmundsson","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Giri","family":"Narasimhan","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Michiel","family":"Smid","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"167_CR1_167","unstructured":"Abam, M.A., de\u00a0Berg, M., Farshi, M., Gudmundsson, J.: Region-fault tolerant geometric spanners. In: Proceedings of the 18th ACM-SIAM Symposium on Discrete Algorithms, New Orleans, 7\u20139 January 2007"},{"key":"167_CR2_167","doi-asserted-by":"crossref","unstructured":"Arya, S., Das, G., Mount, D.M., Salowe, J.S., Smid, M.: Euclidean spanners: short, thin, and lanky. In: Proceedings of the 27th ACM Symposium on Theory of Computing, pp.\u00a0489\u2013498. Las Vegas, 29 May\u20131 June 1995","DOI":"10.1145\/225058.225191"},{"key":"167_CR3_167","doi-asserted-by":"crossref","unstructured":"Arya, S., Mount, D.M., Smid, M.: Randomized and deterministic algorithms for geometric spanners of small diameter. In: Proceedings of the 35th IEEE Symposium on Foundations of Computer Science, pp.\u00a0703\u2013712. Santa Fe, 20\u201322 November 1994","DOI":"10.1109\/SFCS.1994.365722"},{"issue":"2","key":"167_CR4_167","doi-asserted-by":"publisher","first-page":"91","DOI":"10.1016\/S0925-7721(99)00014-0","volume":"13","author":"S. Arya","year":"1999","unstructured":"Arya, S., Mount, D.M., Smid, M.: Dynamic algorithms for geometric spanners of small diameter: Randomized solutions. Comput. Geom. Theor. Appl. 13(2), 91\u2013107 (1999)","journal-title":"Comput. Geom. Theor. Appl."},{"key":"167_CR5_167","doi-asserted-by":"publisher","first-page":"33","DOI":"10.1007\/BF02523237","volume":"17","author":"S. Arya","year":"1997","unstructured":"Arya, S., Smid, M.: Efficient construction of a bounded-degree spanner with low weight. Algorithmica 17, 33\u201354 (1997)","journal-title":"Algorithmica"},{"key":"167_CR6_167","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. J.\u00a0ACM 42, 67\u201390 (1995)","journal-title":"J. ACM"},{"key":"167_CR7_167","doi-asserted-by":"crossref","unstructured":"Czumaj, A., Lingas, A.: Fast approximation schemes for Euclidean multi-connectivity problems. In: Proceedings of the 27th International Colloquium on Automata, Languages and Programming. Lect. Notes Comput. Sci. 1853, 856\u2013868 (2000)","DOI":"10.1007\/3-540-45022-X_72"},{"issue":"2","key":"167_CR8_167","doi-asserted-by":"publisher","first-page":"207","DOI":"10.1007\/s00454-004-1121-7","volume":"32","author":"A. Czumaj","year":"2004","unstructured":"Czumaj, A., Zhao, H.: Fault-tolerant geometric spanners. Discret. Comput. Geom. 32(2), 207\u2013230 (2004)","journal-title":"Discret. Comput. Geom."},{"key":"167_CR9_167","unstructured":"Das, G.: The visibility graph contains a bounded-degree spanner. In: Proceedings of the 9th Canadian Conference on Computational Geometry, Kingston, 11\u201314 August 1997"},{"key":"167_CR10_167","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.\u00a0Comput. Geom. Appl. 7, 297\u2013315 (1997)","journal-title":"Int. J. Comput. Geom. Appl."},{"key":"167_CR11_167","unstructured":"Das, G., Narasimhan, G., Salowe, J.: A new way to weigh malnourished Euclidean graphs. In: Proceedings of the 6th ACM-SIAM Symposium on Discrete Algorithms, pp.\u00a0215\u2013222. San Francisco, 22\u201324 January 1995"},{"key":"167_CR12_167","doi-asserted-by":"crossref","unstructured":"Farshi, M., Gudmundsson, J.: Experimental study of geometric t-spanners. In: Proceedings of the 13th Annual European Symposium on Algorithms. Lect. Notes Comput. Sci. 3669, 556\u2013567 (2005)","DOI":"10.1007\/11561071_50"},{"key":"167_CR13_167","doi-asserted-by":"crossref","unstructured":"Gao, J., Guibas, L.J., Nguyen, A.: Deformable spanners and applications. In: Proceedings of the 20th ACM Symposium on Computational Geometry, pp.\u00a0190\u2013199, New York, 9\u201311 June 2004","DOI":"10.1145\/997817.997848"},{"issue":"5","key":"167_CR14_167","doi-asserted-by":"publisher","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.\u00a0Comput. 31(5), 1479\u20131500 (2002)","journal-title":"SIAM J. Comput."},{"issue":"3","key":"167_CR15_167","doi-asserted-by":"publisher","first-page":"251","DOI":"10.1007\/BF01758846","volume":"8","author":"C. Levcopoulos","year":"1992","unstructured":"Levcopoulos, C., Lingas, A.: There are planar graphs almost as good as the complete graphs and almost as cheap as minimum spanning trees. Algorithmica 8(3), 251\u2013256 (1992)","journal-title":"Algorithmica"},{"key":"167_CR16_167","doi-asserted-by":"publisher","first-page":"144","DOI":"10.1007\/s00453-001-0075-x","volume":"32","author":"C. Levcopoulos","year":"2002","unstructured":"Levcopoulos, C., Narasimhan, G., Smid, M.: Improved algorithms for constructing fault-tolerant spanners. Algorithmica 32, 144\u2013156 (2002)","journal-title":"Algorithmica"},{"key":"167_CR17_167","first-page":"197","volume-title":"Ad Hoc Wireless Networking","author":"X.Y. Li","year":"2003","unstructured":"Li, X.Y.: Applications of computational geometry in wireless ad hoc networks. In: Cheng, X.Z., Huang, X., Du, D.Z. (eds.) Ad Hoc Wireless Networking, pp. 197\u2013264. Kluwer, Dordrecht (2003)"},{"key":"167_CR18_167","volume-title":"Geometric spanner networks","author":"G. Narasimhan","year":"2006","unstructured":"Narasimhan, G., Smid, M.: Geometric spanner networks. Cambridge University Press, New York (2006)"},{"key":"167_CR19_167","unstructured":"Navarro, G., Paredes, R.: Practical construction of metric t-spanners. In: Proceedings of the 5th Workshop on Algorithm Engineering and Experiments, pp.\u00a069\u201381, 11 January 2003. SIAM Press, Baltimore"},{"key":"167_CR20_167","doi-asserted-by":"crossref","unstructured":"Rao, S., Smith, W.D.: Approximating geometrical graphs via spanners and banyans. In: Proceedings of the 30th ACM Symposium on Theory of Computing, pp.\u00a0540\u2013550. Dallas, 23\u201326 May 1998","DOI":"10.1145\/276698.276868"}],"container-title":["Encyclopedia of Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-0-387-30162-4_167","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,30]],"date-time":"2025-01-30T21:32:57Z","timestamp":1738272777000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-0-387-30162-4_167"}},"subtitle":["2002; Gudmundsson, Levcopoulos, Narasimhan"],"short-title":[],"issued":{"date-parts":[[2008]]},"ISBN":["9780387307701","9780387301624"],"references-count":20,"URL":"https:\/\/doi.org\/10.1007\/978-0-387-30162-4_167","relation":{},"subject":[],"published":{"date-parts":[[2008]]}}}