{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T13:37:57Z","timestamp":1725543477784},"publisher-location":"Berlin, Heidelberg","reference-count":20,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540357537"},{"type":"electronic","value":"9783540357551"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2006]]},"DOI":"10.1007\/11785293_36","type":"book-chapter","created":{"date-parts":[[2006,6,26]],"date-time":"2006-06-26T05:24:10Z","timestamp":1151299450000},"page":"388-399","source":"Crossref","is-referenced-by-count":5,"title":["On Spanners of Geometric Graphs"],"prefix":"10.1007","author":[{"given":"Joachim","family":"Gudmundsson","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Michiel","family":"Smid","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"36_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":"36_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"384","DOI":"10.1007\/3-540-45061-0_32","volume-title":"Automata, Languages and Programming","author":"S. Baswana","year":"2003","unstructured":"Baswana, S., Sen, S.: A simple linear time algorithm for computing a (2k\u2009\u2212\u20091)-spanner of O(n 1\u2009+\u20091\/k ) size in weighted graphs. In: Baeten, J.C.M., Lenstra, J.K., Parrow, J., Woeginger, G.J. (eds.) ICALP 2003. LNCS, vol.\u00a02719, pp. 384\u2013396. Springer, Heidelberg (2003)"},{"key":"36_CR3","first-page":"1","volume":"3","author":"U. Brandes","year":"1998","unstructured":"Brandes, U., Handke, D.: NP-completeness results for minimum planar spanners. Discrete Mathematics and Theoretical Computer Science\u00a03, 1\u201310 (1998)","journal-title":"Discrete Mathematics and Theoretical Computer Science"},{"key":"36_CR4","doi-asserted-by":"publisher","first-page":"187","DOI":"10.1016\/0166-218X(94)90073-6","volume":"48","author":"L. Cai","year":"1994","unstructured":"Cai, L.: NP-completeness of minimum spanner problems. Discrete Applied Mathematics\u00a048, 187\u2013194 (1994)","journal-title":"Discrete Applied Mathematics"},{"key":"36_CR5","doi-asserted-by":"publisher","first-page":"359","DOI":"10.1137\/S0895480192237403","volume":"8","author":"L. Cai","year":"1995","unstructured":"Cai, L., Corneil, D.: Tree spanners. SIAM Journal on Discrete Mathematics\u00a08, 359\u2013387 (1995)","journal-title":"SIAM Journal on Discrete Mathematics"},{"key":"36_CR6","unstructured":"Callahan, P.B., Kosaraju, S.R.: Faster algorithms for some geometric graph problems in higher dimensions. In: Proceedings of the 4th ACM-SIAM Symposium on Discrete Algorithms, pp. 291\u2013300 (1993)"},{"key":"36_CR7","doi-asserted-by":"publisher","first-page":"366","DOI":"10.1137\/S0895480101387893","volume":"16","author":"L.S. Chandran","year":"2003","unstructured":"Chandran, L.S.: A high girth graph construction. SIAM Journal on Discrete Mathematics\u00a016, 366\u2013370 (2003)","journal-title":"SIAM Journal on Discrete Mathematics"},{"key":"36_CR8","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, Amsterdam (2000)"},{"key":"36_CR9","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: Gonzalez, T.F. (ed.) Handbook on Approximation Algorithms and Metaheuristics. Chapman & Hall, CRC, Boca Raton (2006)"},{"key":"36_CR10","doi-asserted-by":"crossref","unstructured":"Gudmundsson, J., Levcopoulos, C., Narasimhan, G., Smid, M.: Approximate distance oracles for geometric graphs. In: Proceedings of the 13th ACM-SIAM Symposium on Discrete Algorithms, pp. 828\u2013837 (2002)","DOI":"10.1007\/3-540-36136-7_32"},{"key":"36_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"508","DOI":"10.1007\/978-3-540-31856-9_42","volume-title":"STACS 2005","author":"J. Gudmundsson","year":"2005","unstructured":"Gudmundsson, J., Narasimhan, G., Smid, M.: Fast pruning of geometric spanners. In: Diekert, V., Durand, B. (eds.) STACS 2005. LNCS, vol.\u00a03404, pp. 508\u2013520. Springer, Heidelberg (2005)"},{"key":"36_CR12","doi-asserted-by":"publisher","first-page":"275","DOI":"10.1016\/0166-218X(94)00058-L","volume":"60","author":"F. Lazebnik","year":"1995","unstructured":"Lazebnik, F., Ustimenko, V.A.: Explicit construction of graphs with an arbitrary large girth and of large size. Discrete Applied Mathematics\u00a060, 275\u2013284 (1995)","journal-title":"Discrete Applied Mathematics"},{"key":"36_CR13","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511813603","volume-title":"Probability and Computing","author":"M. Mitzenmacher","year":"2005","unstructured":"Mitzenmacher, M., Upfal, E.: Probability and Computing. Cambridge University Press, Cambridge (2005)"},{"key":"36_CR14","series-title":"Monographs on Discrete Mathematics and Applications","doi-asserted-by":"publisher","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. Monographs on Discrete Mathematics and Applications. Society for Industrial and Applied Mathematics, Philadelphia (2000)"},{"key":"36_CR15","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.A.: Graph spanners. Journal of Graph Theory\u00a013, 99\u2013116 (1989)","journal-title":"Journal of Graph Theory"},{"key":"36_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"261","DOI":"10.1007\/11523468_22","volume-title":"Automata, Languages and Programming","author":"L. Roditty","year":"2005","unstructured":"Roditty, L., Thorup, M., Zwick, U.: Deterministic constructions of approximate distance oracles and spanners. In: Caires, L., Italiano, G.F., Monteiro, L., Palamidessi, C., Yung, M. (eds.) ICALP 2005. LNCS, vol.\u00a03580, pp. 261\u2013272. Springer, Heidelberg (2005)"},{"key":"36_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":"36_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, Amsterdam (2000)"},{"key":"36_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"},{"key":"36_CR20","doi-asserted-by":"publisher","first-page":"143","DOI":"10.1006\/inco.1997.2641","volume":"136","author":"G. Venkatesan","year":"1997","unstructured":"Venkatesan, G., Rotics, U., Madanlal, M.S., Makowsky, J.A., Pandu Rangan, C.: Restrictions of minimum spanner problems. Information and Computation\u00a0136, 143\u2013164 (1997)","journal-title":"Information and Computation"}],"container-title":["Lecture Notes in Computer Science","Algorithm Theory \u2013 SWAT 2006"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11785293_36.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T07:19:24Z","timestamp":1619507964000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11785293_36"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006]]},"ISBN":["9783540357537","9783540357551"],"references-count":20,"URL":"https:\/\/doi.org\/10.1007\/11785293_36","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2006]]}}}