{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T20:19:14Z","timestamp":1725567554097},"publisher-location":"Berlin, Heidelberg","reference-count":35,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642163661"},{"type":"electronic","value":"9783642163678"}],"license":[{"start":{"date-parts":[[2010,1,1]],"date-time":"2010-01-01T00:00:00Z","timestamp":1262304000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2010]]},"DOI":"10.1007\/978-3-642-16367-8_24","type":"book-chapter","created":{"date-parts":[[2010,10,7]],"date-time":"2010-10-07T15:25:55Z","timestamp":1286465155000},"page":"306-311","source":"Crossref","is-referenced-by-count":1,"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":"24_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":"24_CR2","doi-asserted-by":"publisher","first-page":"88","DOI":"10.1007\/978-3-540-77120-3_10","volume-title":"Algorithms 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: Algorithms and Computation, pp. 88\u201399. Springer, Heidelberg (2007)"},{"issue":"4","key":"24_CR3","doi-asserted-by":"publisher","first-page":"451","DOI":"10.1007\/s004930070001","volume":"20","author":"N. Alon","year":"2000","unstructured":"Alon, N., Fischer, E., Krivelevich, M., Szegedy, M.: Efficient Testing of Large Graphs. Combinatorica\u00a020(4), 451\u2013476 (2000)","journal-title":"Combinatorica"},{"issue":"1","key":"24_CR4","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":"24_CR5","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. Discrete and Computational Geometry\u00a039(1-3), 17\u201337 (2007)","journal-title":"Discrete and Computational Geometry"},{"key":"24_CR6","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 Annual ACM Symposium on Theory of Computing (STOC), pp. 489\u2013498 (1995)","DOI":"10.1145\/225058.225191"},{"issue":"1","key":"24_CR7","doi-asserted-by":"publisher","first-page":"73","DOI":"10.1137\/060652294","volume":"21","author":"C. Avart","year":"2007","unstructured":"Avart, C., R\u00f6dl, V., Schacht, M.: Every Monotone 3-Graph Property is Testable. SIAM Journal on Discrete Mathematics\u00a021(1), 73\u201392 (2007)","journal-title":"SIAM Journal on Discrete Mathematics"},{"key":"24_CR8","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":"24_CR9","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":"24_CR10","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 Annual ACM Symposium on Theory of Computing (STOC), pp. 393\u2013402 (2008)","DOI":"10.1145\/1374376.1374433"},{"key":"24_CR11","doi-asserted-by":"crossref","unstructured":"Blais, E.: Testing juntas nearly optimally. In: Proceedings of the 41st Annual ACM Symposium on Theory of Computing (STOC), pp. 151\u2013158 (2009)","DOI":"10.1145\/1536414.1536437"},{"key":"24_CR12","doi-asserted-by":"crossref","unstructured":"Blum, M., Luby, M., Rubinfeld, R.: Self-Testing\/Correcting with Applications to Numerical Problems. In: Proceedings of the 22nd Annual ACM Symposium on Theory of Computing (STOC), pp. 73\u201383 (1990)","DOI":"10.1145\/100216.100225"},{"key":"24_CR13","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)"},{"issue":"3","key":"24_CR14","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 Journal on Computing\u00a035(3), 627\u2013646 (2006)","journal-title":"SIAM Journal on Computing"},{"key":"24_CR15","doi-asserted-by":"crossref","unstructured":"Clarkson, K.L.: Approximating algorithms for shortest path motion planning. In: Proceedings of the 19th ACM Symposium on the Theory of Computation, pp. 56\u201365 (1987)","DOI":"10.1145\/28395.28402"},{"issue":"1","key":"24_CR16","doi-asserted-by":"publisher","first-page":"91","DOI":"10.1137\/S0097539703435297","volume":"35","author":"A. Czumaj","year":"2005","unstructured":"Czumaj, A., Ergun, F., Fortnow, L., Magen, A., Newman, I., Rubinfeld, R., Sohler, C.: Approximating the Weight of the Euclidean Minimum Spanning Tree in Sublinear Time. SIAM Journal on Computing\u00a035(1), 91\u2013109 (2005)","journal-title":"SIAM Journal on Computing"},{"issue":"1","key":"24_CR17","doi-asserted-by":"publisher","first-page":"37","DOI":"10.1016\/j.tcs.2004.09.031","volume":"331","author":"A. Czumaj","year":"2005","unstructured":"Czumaj, A., Sohler, C.: Testing hypergraph colorability. Theoretical Computer Science\u00a0331(1), 37\u201352 (2005)","journal-title":"Theoretical Computer Science"},{"issue":"6","key":"24_CR18","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 non-expanding bounded-degree graphs. SIAM Journal on Computing\u00a038(6), 2499\u20132510 (2009)","journal-title":"SIAM Journal on Computing"},{"key":"24_CR19","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":"24_CR20","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)"},{"issue":"3","key":"24_CR21","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/1367064.1367071","volume":"4","author":"Artur Czumaj","year":"2008","unstructured":"Czumaj, A., Sohler, C.: Testing Euclidean minimum spanning trees in the plane. ACM Transactions on Algorithms\u00a04(3) (2008)","journal-title":"ACM Transactions on Algorithms"},{"issue":"3","key":"24_CR22","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. Journal of Computer and System Sciences\u00a060(3), 717\u2013751 (2000)","journal-title":"Journal of Computer and System Sciences"},{"issue":"1","key":"24_CR23","doi-asserted-by":"publisher","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":"24_CR24","doi-asserted-by":"crossref","unstructured":"Farshi, M., Giannopoulos, P., Gudmundsson, J.: Finding the best shortcut in a geometric network. In: Proceedings of the 21th Annual Symposium on Computational Geometry, pp. 327\u2013335 (2005)","DOI":"10.1145\/1064092.1064143"},{"key":"24_CR25","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 Annual ACM Symposium on Theory of Computing (STOC), pp. 474\u2013483 (2002)","DOI":"10.1145\/509907.509977"},{"issue":"3","key":"24_CR26","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":"24_CR27","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. Journal of the ACM\u00a045(4), 653\u2013750 (1998)","journal-title":"Journal of the ACM"},{"issue":"2","key":"24_CR28","doi-asserted-by":"publisher","first-page":"302","DOI":"10.1007\/s00453-001-0078-7","volume":"32","author":"O. Goldreich","year":"2002","unstructured":"Goldreich, O., Ron, D.: Property Testing in Bounded Degree Graphs. Algorithmica\u00a032(2), 302\u2013343 (2002)","journal-title":"Algorithmica"},{"key":"24_CR29","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","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":"24_CR30","doi-asserted-by":"crossref","unstructured":"Kaufman, T., Sudan, M.: Algebraic property testing: the role of invariance. In: Proceedings of the 40th Annual ACM Symposium on Theory of Computing (STOC), pp. 403\u2013412 (2008)","DOI":"10.1145\/1374376.1374434"},{"issue":"3","key":"24_CR31","doi-asserted-by":"crossref","first-page":"978","DOI":"10.1137\/S0097539799361671","volume":"30","author":"Giri Narasimhan","year":"2000","unstructured":"Narasimhan, G., Smid, M.: Approximating the Stretch Factor of Euclidean Graphs. SIAM Journal on Computing, 978\u2013989 (2000)","journal-title":"SIAM Journal on Computing"},{"key":"24_CR32","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":"24_CR33","doi-asserted-by":"publisher","first-page":"165","DOI":"10.1002\/rsa.10013","volume":"20","author":"M. Parnas","year":"2002","unstructured":"Parnas, M., Ron, D.: Testing the diameter of graphs. Random Structures & Algorithms\u00a020(2), 165\u2013183 (2002)","journal-title":"Random Structures & Algorithms"},{"key":"24_CR34","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"469","DOI":"10.1007\/978-3-540-30538-5_39","volume-title":"FSTTCS 2004: Foundations of Software Technology and Theoretical Computer Science","author":"L. Rademacher","year":"2004","unstructured":"Rademacher, L., Vempala, S.: Testing Geometric Convexity. In: Lodaya, K., Mahajan, M. (eds.) FSTTCS 2004. LNCS, vol.\u00a03328, pp. 469\u2013480. Springer, Heidelberg (2004)"},{"issue":"2","key":"24_CR35","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","Property Testing"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-16367-8_24","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,6,5]],"date-time":"2019-06-05T09:10:44Z","timestamp":1559725844000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-16367-8_24"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010]]},"ISBN":["9783642163661","9783642163678"],"references-count":35,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-16367-8_24","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2010]]}}}