{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,18]],"date-time":"2025-02-18T23:40:23Z","timestamp":1739922023346,"version":"3.37.3"},"publisher-location":"Berlin, Heidelberg","reference-count":19,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540249986"},{"type":"electronic","value":"9783540318569"}],"license":[{"start":{"date-parts":[[2005,1,1]],"date-time":"2005-01-01T00:00:00Z","timestamp":1104537600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2005]]},"DOI":"10.1007\/978-3-540-31856-9_42","type":"book-chapter","created":{"date-parts":[[2010,3,2]],"date-time":"2010-03-02T18:06:19Z","timestamp":1267553179000},"page":"508-520","source":"Crossref","is-referenced-by-count":9,"title":["Fast Pruning of 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":"42_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 & Computational Geometry\u00a09, 81\u2013100 (1993)","journal-title":"Discrete & Computational Geometry"},{"key":"42_CR2","doi-asserted-by":"crossref","unstructured":"Arya, S., Das, G., Mount, D.M., Salowe, J.S., Smid, M.: Euclidean spanners: short, thin, and lanky. In: Proc. 27th ACM Symposium on Theory of Computing, pp. 489\u2013498 (1995)","DOI":"10.1145\/225058.225191"},{"key":"42_CR3","doi-asserted-by":"crossref","unstructured":"Arya, S., Mount, D.M., Smid, M.: Randomized and deterministic algorithms for geometric spanners of small diameter. In: Proc. 35th IEEE Symposium on Foundations of Computer Science, pp. 703\u2013712 (1994)","DOI":"10.1109\/SFCS.1994.365722"},{"key":"42_CR4","doi-asserted-by":"crossref","first-page":"11","DOI":"10.1016\/j.comgeo.2004.01.003","volume":"28","author":"P. Bose","year":"2004","unstructured":"Bose, P., Gudmundsson, J., Morin, P.: Ordered theta graphs. Computational Geometry: Theory and Applications\u00a028, 11\u201318 (2004)","journal-title":"Computational Geometry: Theory and Applications"},{"key":"42_CR5","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"},{"key":"42_CR6","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. International Journal of Computational Geometry and Applications\u00a05, 124\u2013144 (1995)","journal-title":"International Journal of Computational Geometry and Applications"},{"key":"42_CR7","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. International Journal of Computational Geometry and Applications\u00a07, 297\u2013315 (1997)","journal-title":"International Journal of Computational Geometry and Applications"},{"key":"42_CR8","unstructured":"Das, G., Narasimhan, G., Salowe, J.: A new way to weigh malnourished Euclidean graphs. In: Proc. 6th ACM-SIAM Symposium on Discrete Algorithms (1995)"},{"key":"42_CR9","doi-asserted-by":"publisher","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 Science Publishers, Amsterdam (2000)"},{"issue":"5","key":"42_CR10","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 Journal of Computing\u00a031(5), 1479\u20131500 (2002)","journal-title":"SIAM Journal of Computing"},{"key":"42_CR11","doi-asserted-by":"crossref","unstructured":"Gudmundsson, J., Levcopoulos, C., Narasimhan, G., Smid, M.: Approximate distance oracles for geometric graph. In: Proc. 13th ACM-SIAM Symposium on Discrete Algorithms, pp. 828\u2013837 (2002)","DOI":"10.1007\/3-540-36136-7_32"},{"key":"42_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"357","DOI":"10.1007\/3-540-36136-7_32","volume-title":"Algorithms and Computation","author":"J. Gudmundsson","year":"2002","unstructured":"Gudmundsson, J., Levcopoulos, C., Narasimhan, G., Smid, M.: Approximate distance oracles revisited. In: Bose, P., Morin, P. (eds.) ISAAC 2002. LNCS, vol.\u00a02518, pp. 357\u2013368. Springer, Heidelberg (2002)"},{"key":"42_CR13","unstructured":"Gudmundsson, J., Levcopoulos, C., Narasimhan, G., Smid, M.: Approximate distance oracles for geometric spanners. Technical report TR-04-08, Carleton University, School of Computer Science (2004)"},{"key":"42_CR14","doi-asserted-by":"crossref","unstructured":"Keil, J.M.: Approximating the complete Euclidean graph. In: Proc. 1st Scandinavian Workshop on Algorithmic Theory, pp. 208\u2013213 (1988)","DOI":"10.1007\/3-540-19487-8_23"},{"key":"42_CR15","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\u00a032, 144\u2013156 (2002)","journal-title":"Algorithmica"},{"key":"42_CR16","doi-asserted-by":"publisher","first-page":"978","DOI":"10.1137\/S0097539799361671","volume":"30","author":"G. Narasimhan","year":"2000","unstructured":"Narasimhan, G., Smid, M.: Approximating the stretch factor of Euclidean graphs. SIAM Journal on Computing\u00a030, 978\u2013989 (2000)","journal-title":"SIAM Journal on Computing"},{"key":"42_CR17","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1142\/S0218195991000098","volume":"1","author":"J.S. Salowe","year":"1991","unstructured":"Salowe, J.S.: Constructing multidimensional spanner graphs. International Journal of Computational Geometry & Applications\u00a01, 99\u2013107 (1991)","journal-title":"International Journal of Computational Geometry & Applications"},{"key":"42_CR18","doi-asserted-by":"publisher","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 Science Publishers, Amsterdam (2000)"},{"key":"42_CR19","doi-asserted-by":"publisher","first-page":"369","DOI":"10.1007\/BF02574695","volume":"6","author":"P.M. Vaidya","year":"1991","unstructured":"Vaidya, P.M.: A sparse graph almost as good as the complete graph on points in K dimensions. Discrete Computational Geometry\u00a06, 369\u2013381 (1991)","journal-title":"Discrete Computational Geometry"}],"container-title":["Lecture Notes in Computer Science","STACS 2005"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-31856-9_42","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,2,18]],"date-time":"2025-02-18T23:09:43Z","timestamp":1739920183000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-31856-9_42"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005]]},"ISBN":["9783540249986","9783540318569"],"references-count":19,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-31856-9_42","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2005]]}}}