{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T19:14:59Z","timestamp":1725563699556},"publisher-location":"Berlin, Heidelberg","reference-count":34,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642157745"},{"type":"electronic","value":"9783642157752"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2010]]},"DOI":"10.1007\/978-3-642-15775-2_6","type":"book-chapter","created":{"date-parts":[[2010,9,1]],"date-time":"2010-09-01T14:47:32Z","timestamp":1283352452000},"page":"60-71","source":"Crossref","is-referenced-by-count":0,"title":["Testing Euclidean Spanners"],"prefix":"10.1007","author":[{"given":"Frank","family":"Hellweg","sequence":"first","affiliation":[]},{"given":"Melanie","family":"Schmidt","sequence":"additional","affiliation":[]},{"given":"Christian","family":"Sohler","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"issue":"3","key":"6_CR1","doi-asserted-by":"publisher","first-page":"393","DOI":"10.1137\/S0895480102410973","volume":"16","author":"N. Alon","year":"2003","unstructured":"Alon, N., Dar, S., Parnas, M., Ron, D.: Testing of Clustering. SIAM Journal on Discrete Mathematics\u00a016(3), 393\u2013417 (2003)","journal-title":"SIAM Journal on Discrete Mathematics"},{"key":"6_CR2","doi-asserted-by":"publisher","first-page":"88","DOI":"10.1007\/978-3-540-77120-3_10","volume-title":"Algorthims and Computation","author":"H.-K. Ahn","year":"2007","unstructured":"Ahn, H.-K., Farshi, M., Knauer, C., Smid, M., Wang, Y.: Dilation-Optimal Edge Deletion in Polygonal Cycles. In: Algorthims and Computation, pp. 88\u201399. Springer, Heidelberg (2007)"},{"issue":"1","key":"6_CR3","doi-asserted-by":"publisher","first-page":"143","DOI":"10.1137\/060667177","volume":"39","author":"N. Alon","year":"2009","unstructured":"Alon, N., Fischer, E., Newman, I., Shapira, A.: A combinatorial characterization of the testable graph properties: it\u2019s all about regularity. SIAM Journal on Computing\u00a039(1), 143\u2013167 (2009)","journal-title":"SIAM Journal on Computing"},{"issue":"1-3","key":"6_CR4","doi-asserted-by":"publisher","first-page":"17","DOI":"10.1007\/s00454-007-9019-9","volume":"39","author":"P.K. Agarwal","year":"2007","unstructured":"Agarwal, P.K., Klein, R., Knauer, C., Langerman, S., Morin, P., Sharir, M., Soss, M.: Computing the Detour and Spanning Ratio of Paths, Trees, and Cycles in 2D and 3D. Discr. & Computational Geometry\u00a039(1-3), 17\u201337 (2007)","journal-title":"Discr. & Computational Geometry"},{"key":"6_CR5","doi-asserted-by":"crossref","unstructured":"Arya, S., Das, G., Mount, M., Salowe, J.S., Smid, M.: Euclidean spanners: short, thin, and lanky. In: Proceedings of the 27th Annnual ACM Symposium on the Theory of Computing (STOC), pp. 489\u2013498 (1995)","DOI":"10.1145\/225058.225191"},{"issue":"6","key":"6_CR6","doi-asserted-by":"publisher","first-page":"219","DOI":"10.1016\/j.ipl.2006.12.011","volume":"102","author":"O. Ben-Zwi","year":"2007","unstructured":"Ben-Zwi, O., Lachish, O., Newman, I.: Lower bounds for testing Euclidean Minimum Spanning Trees. Information Processing Letters\u00a0102(6), 219\u2013225 (2007)","journal-title":"Information Processing Letters"},{"key":"6_CR7","doi-asserted-by":"crossref","unstructured":"Batu, T., Fortnow, L., Fischer, E., Kumar, R., Rubinfeld, R., White, P.: Testing Random Variables for Independence and Identity. In: Proceedings of the 42nd IEEE Symposium on Foundations of Computer Science (FOCS), pp. 442\u2013451 (2001)","DOI":"10.1109\/SFCS.2001.959920"},{"key":"6_CR8","doi-asserted-by":"crossref","unstructured":"Batu, T., Fortnow, L., Rubinfeld, R., Smith, W., White, P.: Testing that distributions are close. In: Proceedings of the 41st IEEE Symposium on Foundations of Computer Science (FOCS), pp. 259\u2013269 (2000)","DOI":"10.1109\/SFCS.2000.892113"},{"key":"6_CR9","doi-asserted-by":"crossref","unstructured":"Benjamini, I., Schramm, O., Shapira, A.: Every minor-closed property of sparse graphs is testable. In: Proceedings of the 40th Annnual ACM Symposium on the Theory of Computing (STOC), pp. 393\u2013402 (2008)","DOI":"10.1145\/1374376.1374433"},{"key":"6_CR10","doi-asserted-by":"crossref","unstructured":"Blais, E.: Testing juntas nearly optimally. In: Proceedings of the 41st Annnual ACM Symposium on the Theory of Computing (STOC), pp. 151\u2013158 (2009)","DOI":"10.1145\/1536414.1536437"},{"key":"6_CR11","doi-asserted-by":"crossref","unstructured":"Blum, M., Luby, M., Rubinfeld, R.: Self-Testing\/Correcting with Applications to Numerical Problems. In: Proceedings of the 22nd Annnual ACM Symposium on the Theory of Computing (STOC), pp. 73\u201383 (1990)","DOI":"10.1145\/100216.100225"},{"key":"6_CR12","unstructured":"Callahan, P.B., Kosaraju, S.R.: Faster algorithms for some geometric graph problems in higher dimensions. In: Proceedings of the 4th Annnual ACM-SIAM Symposium on Discr. Algorithms (SODA), pp. 291\u2013300 (1993)"},{"issue":"3","key":"6_CR13","doi-asserted-by":"publisher","first-page":"627","DOI":"10.1137\/S009753970444572X","volume":"35","author":"B. Chazelle","year":"2006","unstructured":"Chazelle, B., Liu, D., Magen, A.: Sublinear Geometric Algorithms. SIAM Journalon Computing\u00a035(3), 627\u2013646 (2006)","journal-title":"SIAM Journalon Computing"},{"key":"6_CR14","doi-asserted-by":"crossref","unstructured":"Clarkson, K.L.: Approximating algorithms for shortest path motion planning. In: Proceedings of the 19th Annnual ACM Symposium on the Theory of Computing (STOC), pp. 56\u201365 (1987)","DOI":"10.1145\/28395.28402"},{"issue":"1","key":"6_CR15","doi-asserted-by":"crossref","first-page":"91","DOI":"10.1137\/S0097539703435297","volume":"35","author":"A. C\u0303zumaj","year":"2005","unstructured":"C\u0303zumaj, A., \u1ebcrg\u00fcn, F., F\u0303ortnow, L., M\u0303agen, A., \u00d1ewman, I., R\u0303ubinfeld, R., S\u0303ohler, C.: Approximating the Weight of the Minimum Spanning Tree in Sublinear Time. SIAM Journal on Comp.\u00a035(1), 91\u2013109 (2005)","journal-title":"SIAM Journal on Comp."},{"issue":"6","key":"6_CR16","doi-asserted-by":"publisher","first-page":"2499","DOI":"10.1137\/070681831","volume":"38","author":"A. Czumaj","year":"2009","unstructured":"Czumaj, A., Shapira, A., Sohler, C.: Testing hereditary properties of nonexpanding bounded-degree graphs. SIAM Journal on Computing\u00a038(6), 2499\u20132510 (2009)","journal-title":"SIAM Journal on Computing"},{"key":"6_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"266","DOI":"10.1007\/3-540-44676-1_22","volume-title":"Algorithms - ESA 2001","author":"A. Czumaj","year":"2001","unstructured":"Czumaj, A., Sohler, C.: Property Testing with Geometric Queries. In: Meyer auf der Heide, F. (ed.) ESA 2001. LNCS, vol.\u00a02161, pp. 266\u2013277. Springer, Heidelberg (2001)"},{"key":"6_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"155","DOI":"10.1007\/3-540-45253-2_15","volume-title":"Algorithms - ESA 2000","author":"A. Czumaj","year":"2000","unstructured":"Czumaj, A., Sohler, C., Ziegler, M.: Property Testing in Computational Geometry. In: Paterson, M. (ed.) ESA 2000. LNCS, vol.\u00a01879, pp. 155\u2013166. Springer, Heidelberg (2000)"},{"key":"6_CR19","doi-asserted-by":"crossref","unstructured":"Czumaj, A., Sohler, C.: Testing Euclidean minimum spanning trees in the plane. ACM Transactions on Alg.\u00a04(3) (2008)","DOI":"10.1145\/1367064.1367071"},{"issue":"3","key":"6_CR20","doi-asserted-by":"publisher","first-page":"904","DOI":"10.1137\/060672121","volume":"39","author":"A. Czumaj","year":"2009","unstructured":"Czumaj, A., Sohler, C.: Estimating the Weight of Metric Minimum Spanning Trees in Sublinear Time. SIAM Journal on Computing\u00a039(3), 904\u2013922 (2009)","journal-title":"SIAM Journal on Computing"},{"issue":"3","key":"6_CR21","doi-asserted-by":"publisher","first-page":"717","DOI":"10.1006\/jcss.1999.1692","volume":"60","author":"F. Ergun","year":"2000","unstructured":"Ergun, F., Kannan, S., Kumar, R., Rubinfeld, R., Viswanathan, M.: Spot-Checkers. J. of Computer and System Sciences\u00a060(3), 717\u2013751 (2000)","journal-title":"J. of Computer and System Sciences"},{"issue":"1","key":"6_CR22","doi-asserted-by":"crossref","first-page":"27","DOI":"10.1016\/j.comgeo.2006.05.007","volume":"37","author":"D. Eppstein","year":"2007","unstructured":"Eppstein, D., Wortman, K.A.: Minimum dilation stars. Computational Geometry: Theory and Applications\u00a037(1), 27\u201337 (2007)","journal-title":"Computational Geometry: Theory and Applications"},{"key":"6_CR23","doi-asserted-by":"crossref","unstructured":"Farshi, M., Giannopoulos, P., Gudmundsson, J.: Finding the best shortcut in a geometric network. In: Proceedings of the 21th Annnual ACM Symposium on Computational Geometry, pp. 327\u2013335 (2005)","DOI":"10.1145\/1064092.1064143"},{"key":"6_CR24","doi-asserted-by":"crossref","unstructured":"Fischer, E., Lehman, E., Newman, I., Raskhodnikova, S., Rubinfeld, R., Samorodnitsky, A.: Monotonicity testing over general poset domains. In: Proceedings of the 34th Annnual ACM Symposium on the Theory of Computing (STOC), pp. 474\u2013483 (2002)","DOI":"10.1145\/509907.509977"},{"issue":"3","key":"6_CR25","doi-asserted-by":"publisher","first-page":"301","DOI":"10.1007\/s004930070011","volume":"20","author":"O. Goldreich","year":"2000","unstructured":"Goldreich, O., Goldwasser, S., Lehman, E., Ron, D., Samorodnitsky, A.: Testing Monotonicity. Combinatorica\u00a020(3), 301\u2013337 (2000)","journal-title":"Combinatorica"},{"issue":"4","key":"6_CR26","doi-asserted-by":"publisher","first-page":"653","DOI":"10.1145\/285055.285060","volume":"45","author":"O. Goldreich","year":"1998","unstructured":"Goldreich, O., Goldwasser, S., Ron, D.: Property Testing and its Connection to Learning and Approximation. J. of the ACM\u00a045(4), 653\u2013750 (1998)","journal-title":"J. of the ACM"},{"key":"6_CR27","doi-asserted-by":"crossref","unstructured":"Har-Peled, S., Mazumdar, S.: On Coresets for k-Means and k-Median Clustering. In: Proceedings of the 36th Annnual ACM Symposium on the Theory of Computing (STOC), pp. 291\u2013300 (2004)","DOI":"10.1145\/1007352.1007400"},{"key":"6_CR28","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"208","DOI":"10.1007\/3-540-19487-8_23","volume-title":"SWAT \u201988","author":"M. Keil","year":"1988","unstructured":"Keil, M.: Approximating the complete Euclidean graph. In: Karlsson, R., Lingas, A. (eds.) SWAT 1988. LNCS, vol.\u00a0318, pp. 208\u2013213. Springer, Heidelberg (1988)"},{"key":"6_CR29","doi-asserted-by":"crossref","unstructured":"Kaufman, T., Sudan, M.: Algebraic property testing: the role of invariance. In: Proceedings of the 40th Annnual ACM Symposium on the Theory of Computing (STOC), pp. 403\u2013412 (2008)","DOI":"10.1145\/1374376.1374434"},{"key":"6_CR30","doi-asserted-by":"crossref","unstructured":"Narasimhan, G., Smid, M.: Approximating the Stretch Factor of Euclidean Graphs. SIAM Journal on Computing, 978\u2013989 (2000)","DOI":"10.1137\/S0097539799361671"},{"key":"6_CR31","doi-asserted-by":"publisher","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)"},{"issue":"2","key":"6_CR32","doi-asserted-by":"publisher","first-page":"165","DOI":"10.1002\/rsa.10013","volume":"20","author":"D. Ron","year":"2002","unstructured":"Ron, D., Parnas, M.: Testing the Diameter of Graphs. Random Structures & Algorithms\u00a020(2), 165\u2013183 (2002)","journal-title":"Random Structures & Algorithms"},{"key":"6_CR33","doi-asserted-by":"crossref","unstructured":"Rademacher, L., Vempala, S.: Testing Geometric Convexity. In: Proceedings of the 24th Foundations of Software Technology and Theoretical Computer Science (FSTTCS), pp. 469\u2013480 (2004)","DOI":"10.1007\/978-3-540-30538-5_39"},{"issue":"2","key":"6_CR34","doi-asserted-by":"publisher","first-page":"252","DOI":"10.1137\/S0097539793255151","volume":"25","author":"R. Rubinfeld","year":"1996","unstructured":"Rubinfeld, R., Sudan, M.: Robust Characterizations of Polynomials with Applications to Program Testing. SIAM Journal on Computing\u00a025(2), 252\u2013271 (1996)","journal-title":"SIAM Journal on Computing"}],"container-title":["Lecture Notes in Computer Science","Algorithms \u2013 ESA 2010"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-15775-2_6","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,6,3]],"date-time":"2019-06-03T00:17:45Z","timestamp":1559521065000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-15775-2_6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010]]},"ISBN":["9783642157745","9783642157752"],"references-count":34,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-15775-2_6","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2010]]}}}