{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,10]],"date-time":"2026-06-10T07:57:29Z","timestamp":1781078249480,"version":"3.54.1"},"publisher-location":"Berlin, Heidelberg","reference-count":26,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783642403279","type":"print"},{"value":"9783642403286","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2013]]},"DOI":"10.1007\/978-3-642-40328-6_29","type":"book-chapter","created":{"date-parts":[[2013,8,16]],"date-time":"2013-08-16T09:17:34Z","timestamp":1376644654000},"page":"411-424","source":"Crossref","is-referenced-by-count":13,"title":["Local Reconstructors and Tolerant Testers for Connectivity and Diameter"],"prefix":"10.1007","author":[{"given":"Andrea","family":"Campagna","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Alan","family":"Guo","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ronitt","family":"Rubinfeld","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","reference":[{"key":"29_CR1","doi-asserted-by":"crossref","unstructured":"Ailon, N., Chazelle, B., Comandur, S., Liu, D.: Property-preserving data reconstruction. In: Proc. 15th International Symposium on Algorithms and Computation, pp. 16\u201327 (2004)","DOI":"10.1007\/978-3-540-30551-4_4"},{"key":"29_CR2","doi-asserted-by":"publisher","first-page":"161","DOI":"10.1002\/1097-0118(200011)35:3<161::AID-JGT1>3.0.CO;2-Y","volume":"35","author":"N. Alon","year":"2000","unstructured":"Alon, N., Gy\u00e0rf\u00e0s, A., Ruszink\u00f2, M.: Decreasing the diameter of bounded degree graphs. J.\u00a0Graph Theory\u00a035, 161\u2013172 (2000)","journal-title":"J.\u00a0Graph Theory"},{"key":"29_CR3","doi-asserted-by":"publisher","first-page":"184","DOI":"10.1002\/rsa.10023","volume":"20","author":"M.A. Bender","year":"2002","unstructured":"Bender, M.A., Ron, D.: Testing properties of directed graphs: acyclicity and connectivity. Random Structures and Algorithms\u00a020, 184\u2013205 (2002)","journal-title":"Random Structures and Algorithms"},{"key":"29_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"448","DOI":"10.1007\/978-3-642-15369-3_34","volume-title":"Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques","author":"A. Bhattacharyya","year":"2010","unstructured":"Bhattacharyya, A., Grigorescu, E., Jha, M., Jung, K., Raskhodnikova, S., Woodruff, D.P.: Lower bounds for local monotonicity reconstruction from transitive-closure spanners. In: Serna, M., Shaltiel, R., Jansen, K., Rolim, J. (eds.) APPROX and RANDOM 2010. LNCS, vol.\u00a06302, pp. 448\u2013461. Springer, Heidelberg (2010)"},{"key":"29_CR5","unstructured":"Brakerski, Z.: Local property restoring. Manuscript (2008)"},{"key":"29_CR6","unstructured":"Campagna, A., Guo, A., Rubinfeld, R.: Local reconstructors and tolerant testers for connectivity and diameter. ArXiv preprint. arXiv.DS:1208.2956"},{"issue":"6","key":"29_CR7","doi-asserted-by":"publisher","first-page":"1370","DOI":"10.1137\/S0097539702403244","volume":"34","author":"B. Chazelle","year":"2005","unstructured":"Chazelle, B., Rubinfeld, R., Trevisan, L.: Approximating the Minimum Spanning Tree Weight in Sublinear Time. SIAM J. Comput.\u00a034(6), 1370\u20131379 (2005)","journal-title":"SIAM J. Comput."},{"key":"29_CR8","doi-asserted-by":"crossref","unstructured":"Chazelle, B., Seshadhri, C.: Online geometric reconstruction. In: Proc. 22nd ACM Symposium on Computational Geometry, pp. 386\u2013394 (2006)","DOI":"10.1145\/1137856.1137912"},{"key":"29_CR9","doi-asserted-by":"crossref","unstructured":"Derbakova, A., Correll, N., Rus, D.: Decentralized self-repair to maintain connectivity and coverage in networked multi-robot systems. In: Proc. IEEE International Conference on Robotics and Automation (2011)","DOI":"10.1109\/ICRA.2011.5980367"},{"issue":"4","key":"29_CR10","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. ACM\u00a045(4), 653\u2013750 (1998)","journal-title":"J. ACM"},{"key":"29_CR11","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, 302\u2013343 (2002)","journal-title":"Algorithmica"},{"key":"29_CR12","unstructured":"Jha, M., Raskhodnikova, S.: Testing and reconstruction of Lipschitz functions with applications to data privacy. In: Proc. 52nd Annual IEEE Symposium on Foundations of Computer Science, pp. 433\u2013442"},{"key":"29_CR13","doi-asserted-by":"crossref","unstructured":"Kale, S., Peres, Y., Seshadhri, C.: Noise tolerance of expanders and sublinear expander reconstruction. In: Proc. 49th Annual IEEE Symposium on Foundations of Computer Science, pp. 719\u2013728 (2008)","DOI":"10.1109\/FOCS.2008.65"},{"issue":"4","key":"29_CR14","doi-asserted-by":"publisher","first-page":"1036","DOI":"10.1137\/0215074","volume":"15","author":"M. Luby","year":"1986","unstructured":"Luby, M.: A simple parallel algorithm for the maximal independent set problem. SIAM Journal on Computing\u00a015(4), 1036\u20131053 (1986)","journal-title":"SIAM Journal on Computing"},{"key":"29_CR15","doi-asserted-by":"crossref","unstructured":"Marko, S., Ron, D.: Approximating the distance to properties in bounded-degree and general sparse graphs. ACM Transactions on Algorithms\u00a05(2) (2009)","DOI":"10.1145\/1497290.1497298"},{"key":"29_CR16","doi-asserted-by":"crossref","first-page":"96","DOI":"10.4064\/fm-10-1-96-115","volume":"10","author":"K. Menger","year":"1927","unstructured":"Menger, K.: Zur allgemeinen Kurventheorie. Fund. Math.\u00a010, 96\u2013115 (1927)","journal-title":"Fund. Math."},{"key":"29_CR17","doi-asserted-by":"crossref","unstructured":"Nguyen, H.N., Onak, K.: Constant-time approximation algorithms via local improvements. In: Proc. 49th Annual IEEE Symposium on Foundations of Computer Science, pp. 327\u2013336 (2008)","DOI":"10.1109\/FOCS.2008.81"},{"issue":"4","key":"29_CR18","doi-asserted-by":"crossref","first-page":"1139","DOI":"10.1137\/S0097539792234226","volume":"26","author":"D. Noar","year":"1997","unstructured":"Noar, D., Gusfield, D., Martel, C.: A fast algorithm for optimally increasing the edge connectivity. SICOMP\u00a026(4), 1139\u20131165 (1997)","journal-title":"SICOMP"},{"key":"29_CR19","doi-asserted-by":"crossref","unstructured":"Onak, K., Ron, D., Rosen, M., Rubinfeld, R.: A near-optimal sublinear-time algorithm for approximating the minimum vertex cover size. In: Proc. 23rd Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 1123\u20131131 (2012)","DOI":"10.1137\/1.9781611973099.88"},{"key":"29_CR20","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 and Algorithms\u00a020, 165\u2013183 (2002)","journal-title":"Random Structures and Algorithms"},{"key":"29_CR21","doi-asserted-by":"publisher","first-page":"1012","DOI":"10.1016\/j.jcss.2006.03.002","volume":"72","author":"M. Parnas","year":"2006","unstructured":"Parnas, M., Ron, D., Rubinfeld, R.: Tolerant property testing and distance approximation. Journal of Computer and System Sciences\u00a072, 1012\u20131042 (2006)","journal-title":"Journal of Computer and System Sciences"},{"issue":"2","key":"29_CR22","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 J. Comput.\u00a025(2), 252\u2013271 (1996)","journal-title":"SIAM J. Comput."},{"key":"29_CR23","unstructured":"Rubinfeld, R., Tamir, G., Vardi, S., Xie, N.: Fast local computation algorithms. In: Proc. 2nd Symposium on Innovations in Computer Science, pp. 223\u2013238 (2011)"},{"key":"29_CR24","doi-asserted-by":"publisher","first-page":"2897","DOI":"10.1137\/080728561","volume":"39","author":"M.E. Saks","year":"2010","unstructured":"Saks, M.E., Seshadhri, C.: Local monotonicity reconstruction. SIAM Journal on Computing\u00a039, 2897\u20132926 (2010)","journal-title":"SIAM Journal on Computing"},{"key":"29_CR25","doi-asserted-by":"crossref","unstructured":"Stump, E., Jadbabaie, A., Kumar, V.: Connectivity management in mobile robot teams. In: Proc. IEEE International Conference on Robotics and Automation (2008)","DOI":"10.1109\/ROBOT.2008.4543418"},{"key":"29_CR26","doi-asserted-by":"crossref","unstructured":"Yoshida, Y., Yamamoto, M., Ito, H.: An improved constant-time approximation algorithm for maximum matchings. In: Proc. 41st ACM Symposium on Theory of Computing, pp. 225\u2013234 (2009)","DOI":"10.1145\/1536414.1536447"}],"container-title":["Lecture Notes in Computer Science","Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-40328-6_29","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,16]],"date-time":"2019-05-16T13:50:16Z","timestamp":1558014616000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-40328-6_29"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013]]},"ISBN":["9783642403279","9783642403286"],"references-count":26,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-40328-6_29","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013]]}}}