{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,10,14]],"date-time":"2024-10-14T04:05:32Z","timestamp":1728878732105},"reference-count":26,"publisher":"Springer Science and Business Media LLC","issue":"11","license":[{"start":{"date-parts":[[2024,9,12]],"date-time":"2024-09-12T00:00:00Z","timestamp":1726099200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2024,9,12]],"date-time":"2024-09-12T00:00:00Z","timestamp":1726099200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"funder":[{"name":"Nazarbayev University Social Policy Grant"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2024,11]]},"DOI":"10.1007\/s00453-024-01248-x","type":"journal-article","created":{"date-parts":[[2024,9,12]],"date-time":"2024-09-12T14:04:51Z","timestamp":1726149891000},"page":"3496-3517","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Testing Connectedness of Images"],"prefix":"10.1007","volume":"86","author":[{"given":"Piotr","family":"Berman","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Meiram","family":"Murzabulatov","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sofya","family":"Raskhodnikova","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Dragos-Florian","family":"Ristache","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2024,9,12]]},"reference":[{"key":"1248_CR1","doi-asserted-by":"crossref","unstructured":"Alon, N., Ben-Eliezer, O., Fischer, E.: Testing hereditary properties of ordered graphs and matrices. In: Umans, C. (ed.) 58th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2017, Berkeley, CA, USA, October 15\u201317, 2017, pp. 848\u2013858. IEEE Computer Society (2017)","DOI":"10.1109\/FOCS.2017.83"},{"key":"1248_CR2","unstructured":"Ben-Eliezer, O., Fischer, E.: Earthmover resilience and testing in ordered structures. In: Servedio, R.A. (ed.) 33rd Computational Complexity Conference, CCC 2018, June 22\u201324, 2018, San Diego, CA, USA, volume 102 of LIPIcs, pp. 18:1\u201318:35. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2018)"},{"issue":"11","key":"1248_CR3","doi-asserted-by":"publisher","first-page":"639","DOI":"10.1016\/j.ipl.2014.05.008","volume":"114","author":"P Berenbrink","year":"2014","unstructured":"Berenbrink, P., Krayenhoff, B., Mallmann-Trenn, F.: Estimating the number of connected components in sublinear time. Inf. Process. Lett. 114(11), 639\u2013642 (2014)","journal-title":"Inf. Process. Lett."},{"key":"1248_CR4","unstructured":"Ben-Eliezer, O., Korman, S., Reichman, D.: Deleting and testing forbidden patterns in multi-dimensional arrays. In: Chatzigiannakis, I., Indyk, P., Kuhn, F., Muscholl, A. (eds.) 44th International Colloquium on Automata, Languages, and Programming, ICALP 2017, July 10\u201314, 2017, Warsaw, Poland, volume\u00a080 of LIPIcs, pp. 9:1\u20139:14. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2017)"},{"issue":"3","key":"1248_CR5","doi-asserted-by":"publisher","first-page":"1247","DOI":"10.1007\/s00453-018-0467-9","volume":"81","author":"P Berman","year":"2019","unstructured":"Berman, P., Murzabulatov, M., Raskhodnikova, S.: The power and limitations of uniform samples in testing properties of figures. Algorithmica 81(3), 1247\u20131266 (2019)","journal-title":"Algorithmica"},{"issue":"3","key":"1248_CR6","doi-asserted-by":"publisher","first-page":"413","DOI":"10.1002\/rsa.20797","volume":"54","author":"P Berman","year":"2019","unstructured":"Berman, P., Murzabulatov, M., Raskhodnikova, S.: Testing figures under the uniform distribution. Random Struct. Algorithms 54(3), 413\u2013443 (2019)","journal-title":"Random Struct. Algorithms"},{"issue":"4","key":"1248_CR7","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/3531527","volume":"18","author":"P Berman","year":"2022","unstructured":"Berman, P., Murzabulatov, M., Raskhodnikova, S.: Tolerant testers of image properties. ACM Trans. Algorithms 18(4), 1\u201339 (2022)","journal-title":"ACM Trans. Algorithms"},{"key":"1248_CR8","unstructured":"Berman, P., Murzabulatov, M., Raskhodnikova, S., Ristache, D.: Testing connectedness of images. In: Megow, N., Smith, A.D. (eds.) Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX\/RANDOM 2023, September 11\u201313, 2023, Atlanta, Georgia, USA, volume 275 of LIPIcs, pp. 66:1\u201366:15. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2023)"},{"key":"1248_CR9","doi-asserted-by":"crossref","unstructured":"Berman, P., Raskhodnikova, S., Yaroslavtsev, G.: $$L_p$$-testing. In: Shmoys, D.B. (ed.) Symposium on Theory of Computing, STOC 2014, New York, NY, USA, May 31\u2013June 03, 2014, pp. 164\u2013173. ACM (2014)","DOI":"10.1145\/2591796.2591887"},{"key":"1248_CR10","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. 34, 1370\u20131379 (2005)","journal-title":"SIAM J. Comput."},{"issue":"3","key":"1248_CR11","doi-asserted-by":"publisher","first-page":"293","DOI":"10.1007\/s00493-007-2154-3","volume":"27","author":"E Fischer","year":"2007","unstructured":"Fischer, E., Newman, I.: Testing of matrix-poset properties. Combinatorica 27(3), 293\u2013327 (2007)","journal-title":"Combinatorica"},{"issue":"4","key":"1248_CR12","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 45(4), 653\u2013750 (1998)","journal-title":"J. ACM"},{"issue":"2","key":"1248_CR13","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 32(2), 302\u2013343 (2002)","journal-title":"Algorithmica"},{"issue":"2","key":"1248_CR14","doi-asserted-by":"publisher","first-page":"256","DOI":"10.1109\/TPAMI.2010.165","volume":"33","author":"I Kleiner","year":"2011","unstructured":"Kleiner, I., Keren, D., Newman, I., Ben-Zwi, O.: Applying property testing to an image partitioning problem. IEEE Trans. Pattern Anal. Mach. Intell. 33(2), 256\u2013265 (2011)","journal-title":"IEEE Trans. Pattern Anal. Mach. Intell."},{"key":"1248_CR15","unstructured":"Korman, S., Reichman, D., Tsur, G.: Tight approximation of image matching. CoRR, arXiv:1111.1713 (2011)"},{"key":"1248_CR16","doi-asserted-by":"crossref","unstructured":"Korman, S., Reichman, D., Tsur, G., Avidan, S.: Fast-match: Fast affine template matching. In: CVPR, pp. 2331\u20132338. IEEE (2013)","DOI":"10.1109\/CVPR.2013.302"},{"issue":"1","key":"1248_CR17","doi-asserted-by":"publisher","first-page":"1:1","DOI":"10.1145\/3488250","volume":"14","author":"A Levi","year":"2022","unstructured":"Levi, A., Pallavoor, R.K.S., Raskhodnikova, S., Varma, N.: Erasure-resilient sublinear-time graph algorithms. ACM Trans. Comput. Theory 14(1), 1:1-1:22 (2022)","journal-title":"ACM Trans. Comput. Theory"},{"key":"1248_CR18","doi-asserted-by":"publisher","DOI":"10.7551\/mitpress\/11301.001.0001","volume-title":"Perceptrons: An Introduction to Computational Geometry","author":"M Minsky","year":"2017","unstructured":"Minsky, M., Papert, S.A.: Perceptrons: An Introduction to Computational Geometry. The MIT Press, Cambridge (2017)"},{"key":"1248_CR19","unstructured":"Murzabulatov, M.: Testing Geometric Properties of Two-Dimensional Figures and Images. PhD thesis, The Pennsylvania State University (2017)"},{"issue":"12","key":"1248_CR20","doi-asserted-by":"publisher","first-page":"4549","DOI":"10.1109\/JSEN.2019.2897989","volume":"19","author":"P Paral","year":"2019","unstructured":"Paral, P., Chatterjee, A., Rakshit, A.: Vision sensor-based shoe detection for human tracking in a human-robot coexisting environment: a photometric invariant approach using dbscan algorithm. IEEE Sens. J. 19(12), 4549\u20134559 (2019)","journal-title":"IEEE Sens. J."},{"issue":"2","key":"1248_CR21","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 Struct. Algorithms 20(2), 165\u2013183 (2002)","journal-title":"Random Struct. Algorithms"},{"key":"1248_CR22","doi-asserted-by":"crossref","unstructured":"Raskhodnikova, S.: Approximate testing of visual properties. In: Arora, S., Jansen, K., Rolim, J.D.P., Sahai, A. (eds.) RANDOM-APPROX, volume 2764 of Lecture Notes in Computer Science, pp. 370\u2013381. Springer (2003)","DOI":"10.1007\/978-3-540-45198-3_31"},{"key":"1248_CR23","unstructured":"Raskhodnikova, S.: Property testing : theory and applications. PhD thesis, Massachusetts Institute of Technology (2003)"},{"issue":"2","key":"1248_CR24","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. 25(2), 252\u2013271 (1996)","journal-title":"SIAM J. Comput."},{"issue":"4","key":"1248_CR25","doi-asserted-by":"publisher","first-page":"17:1","DOI":"10.1145\/2635806","volume":"10","author":"D Ron","year":"2014","unstructured":"Ron, D., Tsur, G.: Testing properties of sparse images. ACM Trans. Algorithms 10(4), 17:1-17:52 (2014)","journal-title":"ACM Trans. Algorithms"},{"key":"1248_CR26","doi-asserted-by":"crossref","unstructured":"Yao, A.C.: Probabilistic computation, towards a unified measure of complexity. In: Proceedings of the Eighteenth Annual Symposium on Foundations of Computer Science, pp. 222\u2013227 (1977)","DOI":"10.1109\/SFCS.1977.24"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-024-01248-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-024-01248-x\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-024-01248-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,10,13]],"date-time":"2024-10-13T09:02:06Z","timestamp":1728810126000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-024-01248-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,9,12]]},"references-count":26,"journal-issue":{"issue":"11","published-print":{"date-parts":[[2024,11]]}},"alternative-id":["1248"],"URL":"https:\/\/doi.org\/10.1007\/s00453-024-01248-x","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2024,9,12]]},"assertion":[{"value":"21 November 2023","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"23 June 2024","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"12 September 2024","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare no competing interests.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Competing interests"}}]}}