{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:44:51Z","timestamp":1740109491431,"version":"3.37.3"},"reference-count":25,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2020,1,20]],"date-time":"2020-01-20T00:00:00Z","timestamp":1579478400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2020,1,20]],"date-time":"2020-01-20T00:00:00Z","timestamp":1579478400000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["comput. complex."],"published-print":{"date-parts":[[2020,6]]},"DOI":"10.1007\/s00037-019-00191-6","type":"journal-article","created":{"date-parts":[[2020,1,20]],"date-time":"2020-01-20T08:02:46Z","timestamp":1579507366000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["On the characterization of 1-sided error strongly testable graph properties for bounded-degree graphs"],"prefix":"10.1007","volume":"29","author":[{"given":"Hiro","family":"Ito","sequence":"first","affiliation":[]},{"given":"Areej","family":"Khoury","sequence":"additional","affiliation":[]},{"given":"Ilan","family":"Newman","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2020,1,20]]},"reference":[{"key":"191_CR1","doi-asserted-by":"crossref","unstructured":"Noga Alon, Eldar Fischer, Ilan Newman & Asaf Shapira (2009). A Combinatorial Characterization of the Testable Graph Properties: It's All About Regularity. SIAM J. Comput.39(1), 143\u2013167. URL http:\/\/dx.doi.org\/10.1137\/060667177","DOI":"10.1137\/060667177"},{"key":"191_CR2","doi-asserted-by":"crossref","unstructured":"Noga Alon & Asaf Shapira (2006). A Characterization of Easily Testable Induced Subgraphs. Combinatorics, Probability & Computing15(6), 791\u2013805. URL http:\/\/dx.doi.org\/10.1017\/S0963548306007759","DOI":"10.1017\/S0963548306007759"},{"key":"191_CR3","doi-asserted-by":"crossref","unstructured":"Noga Alon & Asaf Shapira (2008). A Characterization of the (Natural) Graph Properties Testable with One-Sided Error. SIAM J. Comput.37(6), 1703\u20131727. URL http:\/\/dx.doi.org\/10.1137\/06064888X","DOI":"10.1137\/06064888X"},{"key":"191_CR4","doi-asserted-by":"crossref","unstructured":"Michael A. Bender & Dana Ron (2002). Testing properties of directed graphs: acyclicity and connectivity. Random Struct. Algorithms20(2), 184\u2013205. URL http:\/\/dx.doi.org\/10.1002\/rsa.10023","DOI":"10.1002\/rsa.10023"},{"issue":"2","key":"191_CR5","doi-asserted-by":"publisher","first-page":"139","DOI":"10.1002\/rsa.20462","volume":"45","author":"Artur Czumaj","year":"2014","unstructured":"Czumaj, Artur, Goldreich, Oded, Dana Ron, C., Seshadhri, Asaf Shapira, Sohler, Christian: Finding cycles and trees in sublinear time. Random Struct. Algorithms 45(2), 139\u2013184 (2014)","journal-title":"Random Struct. Algorithms"},{"key":"191_CR6","doi-asserted-by":"crossref","unstructured":"Artur Czumaj, Pan Peng & Christian Sohler (2015). Testing Cluster Structure of Graphs. In Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, Portland, OR, USA, STOC '15, 723\u2013732","DOI":"10.1145\/2746539.2746618"},{"key":"191_CR7","doi-asserted-by":"crossref","unstructured":"Artur Czumaj, Pan Peng & Christian Sohler (2016). Relating Two Property Testing Models for Bounded Degree Directed Graphs. In Proceedings of the Forty-eighth Annual ACM Symposium on Theory of Computing, STOC '16, 1033-1045. ISBN 978-1-4503-4132-5. URL http:\/\/doi.acm.org\/10.1145\/2897518.2897575","DOI":"10.1145\/2897518.2897575"},{"key":"191_CR8","doi-asserted-by":"crossref","unstructured":"Artur Czumaj, Asaf Shapira & Christian Sohler (2009). Testing Hereditary Properties of Nonexpanding Bounded-Degree Graphs. SIAM J. Comput.38(6), 2499\u20132510. URL http:\/\/dx.doi.org\/10.1137\/070681831","DOI":"10.1137\/070681831"},{"key":"191_CR9","doi-asserted-by":"crossref","unstructured":"Artur Czumaj & Christian Sohler (2010). Testing Expansion in Bounded-Degree Graphs. Combinatorics, Probability & Computing19(5-6), 693\u2013709. URL http:\/\/dx.doi.org\/10.1017\/S096354831000012X","DOI":"10.1017\/S096354831000012X"},{"key":"191_CR10","doi-asserted-by":"crossref","unstructured":"Oded Goldreich, Shafi Goldwasser & Dana Ron (1998). Property Testing and its Connection to Learning and Approximation. J. ACM45(4), 653\u2013750. URL http:\/\/doi.acm.org\/10.1145\/285055.285060","DOI":"10.1145\/285055.285060"},{"issue":"3","key":"191_CR11","doi-asserted-by":"publisher","first-page":"335","DOI":"10.1007\/s004930050060","volume":"19","author":"Oded Goldreich & Dana Ron","year":"1999","unstructured":"Oded Goldreich & Dana Ron: A Sublinear Bipartiteness Tester for Bounded Degree Graphs. Combinatorica 19(3), 335\u2013373 (1999)","journal-title":"Combinatorica"},{"key":"191_CR12","doi-asserted-by":"crossref","unstructured":"Oded Goldreich & Dana Ron (2002). Property Testing in Bounded Degree Graphs. Algorithmica32(2), 302\u2013343. URL http:\/\/dx.doi.org\/10.1007\/s00453-001-0078-7","DOI":"10.1007\/s00453-001-0078-7"},{"issue":"2","key":"191_CR13","doi-asserted-by":"publisher","first-page":"534","DOI":"10.1137\/100789646","volume":"40","author":"Oded Goldreich & Dana Ron","year":"2011","unstructured":"Oded Goldreich & Dana Ron: On Proximity-Oblivious Testing. SIAM J. Comput. 40(2), 534\u2013566 (2011a)","journal-title":"SIAM J. Comput."},{"key":"191_CR14","doi-asserted-by":"crossref","unstructured":"Oded Goldreich & Dana Ron (2011b). On Testing Expansion in Bounded-Degree Graphs. In Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation, 68-75. URL https:\/\/doi.org\/10.1007\/978-3-642-22670-0_9","DOI":"10.1007\/978-3-642-22670-0_9"},{"key":"191_CR15","doi-asserted-by":"crossref","unstructured":"Oded Goldreich & Luca Trevisan (2003). Three theorems regarding testing graph properties. Random Struct. Algorithms23(1), 23\u201357. URL https:\/\/doi.org\/10.1002\/rsa.10078","DOI":"10.1002\/rsa.10078"},{"key":"#cr-split#-191_CR16.1","doi-asserted-by":"crossref","unstructured":"Avinatan Hassidim, Jonathan A. Kelner, Huy N. Nguyen & Krzysztof Onak (2009). Local Graph Partitions for Approximation and Testing. In 50th Annual IEEE Symposium on Foundations of","DOI":"10.1109\/FOCS.2009.77"},{"key":"#cr-split#-191_CR16.2","unstructured":"Computer Science, FOCS 2009, October 25-27, 2009, Atlanta, Georgia, USA, 22-31."},{"key":"191_CR17","unstructured":"Hiro Ito, Areej Khoury & Ilan Newman (2019). On the Characterization of $$1$$-sided error Strongly Testable Graph Properties for bounded-degree graphs, including an appendix, arxive cs.CC 1909.09984"},{"key":"191_CR18","unstructured":"Reut Levi & Dana Ron (2015). A Quasi-Polynomial Time Partition Oracle for Graphs with an Excluded Minor. ACM Trans. Algorithms11(3), 24:1\u201324:13. URL http:\/\/doi.acm.org\/10.1145\/2629508"},{"key":"191_CR19","doi-asserted-by":"crossref","unstructured":"Asaf Nachmias & Asaf Shapira (2010). Testing the expansion of a graph. Inf. Comput.208(4), 309\u2013314. URL https:\/\/doi.org\/10.1016\/j.ic.2009.09.002","DOI":"10.1016\/j.ic.2009.09.002"},{"key":"191_CR20","doi-asserted-by":"crossref","unstructured":"Ilan Newman & Christian Sohler (2013). Every Property of Hyperfinite Graphs Is Testable. SIAM J. Comput.42(3), 1095\u20131112. URL http:\/\/dx.doi.org\/10.1137\/120890946","DOI":"10.1137\/120890946"},{"key":"191_CR21","unstructured":"Huy N. Nguyen & Krzysztof Onak (2008). Constant-Time Approximation Algorithms via Local Improvements. In 49th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2008, October 25-28, 2008, Philadelphia, PA, USA, 327\u2013336."},{"key":"191_CR22","doi-asserted-by":"crossref","unstructured":"Yaron Orenstein & Dana Ron (2011). Testing Eulerianity and connectivity in directed sparse graphs. Theor. Comput. Sci.412(45), 6390\u20136408. URL http:\/\/dx.doi.org\/10.1016\/j.tcs.2011.06.038","DOI":"10.1016\/j.tcs.2011.06.038"},{"key":"191_CR23","doi-asserted-by":"crossref","unstructured":"Michal Parnas & Dana Ron (2002). Testing the diameter of graphs. Random Struct. Algorithms20(2), 165\u2013183. URL http:\/\/dx.doi.org\/10.1002\/rsa.10013","DOI":"10.1002\/rsa.10013"},{"key":"191_CR24","doi-asserted-by":"crossref","unstructured":"Yuichi Yoshida & Hiro Ito (2010). Testing k-edge-connectivity of digraphs. J. Systems Science & Complexity 23(1), 91\u2013101. URL http:\/\/dx.doi.org\/10.1007\/s11424-010-9280-5.","DOI":"10.1007\/s11424-010-9280-5"}],"container-title":["computational complexity"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00037-019-00191-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00037-019-00191-6\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00037-019-00191-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,1,19]],"date-time":"2021-01-19T00:08:10Z","timestamp":1611014890000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00037-019-00191-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,1,20]]},"references-count":25,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2020,6]]}},"alternative-id":["191"],"URL":"https:\/\/doi.org\/10.1007\/s00037-019-00191-6","relation":{},"ISSN":["1016-3328","1420-8954"],"issn-type":[{"type":"print","value":"1016-3328"},{"type":"electronic","value":"1420-8954"}],"subject":[],"published":{"date-parts":[[2020,1,20]]},"assertion":[{"value":"14 May 2019","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"20 January 2020","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"1"}}