{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T22:49:57Z","timestamp":1725490197830},"publisher-location":"Berlin, Heidelberg","reference-count":14,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540742074"},{"type":"electronic","value":"9783540742081"}],"license":[{"start":{"date-parts":[[2007,1,1]],"date-time":"2007-01-01T00:00:00Z","timestamp":1167609600000},"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":[[2007]]},"DOI":"10.1007\/978-3-540-74208-1_28","type":"book-chapter","created":{"date-parts":[[2007,8,27]],"date-time":"2007-08-27T14:52:26Z","timestamp":1188226346000},"page":"380-394","source":"Crossref","is-referenced-by-count":10,"title":["Testing st-Connectivity"],"prefix":"10.1007","author":[{"given":"Sourav","family":"Chakraborty","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Eldar","family":"Fischer","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Oded","family":"Lachish","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Arie","family":"Matsliah","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ilan","family":"Newman","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"28_CR1","first-page":"251","volume-title":"Proceedings of the 38 th ACM STOC","author":"N. Alon","year":"2006","unstructured":"Alon, N., Fischer, E., Newman, I., Shapira, A.: A Combinatorial Characterization of the Testable Graph Properties: It\u2019s All About Regularity. In: Proceedings of the 38 th ACM STOC, pp. 251\u2013260. ACM, New York (2006)"},{"key":"28_CR2","doi-asserted-by":"crossref","unstructured":"Alon, N., Kaufman, T., Krivilevich, M., Ron, D.: Testing triangle-freeness in general graphs. In: Proceedings of the 17 th SODA, pp. 279\u2013288 (2006)","DOI":"10.1145\/1109557.1109589"},{"key":"28_CR3","doi-asserted-by":"crossref","unstructured":"Alon, N., Shapira, A.: A Characterization of the (natural) Graph Properties Testable with One-Sided Error. In: Proceedings of the 46 th IEEE FOCS, pp. 429\u2013438 (2005) Also SIAM Journal on Computing (to appear)","DOI":"10.1109\/SFCS.2005.5"},{"key":"28_CR4","doi-asserted-by":"crossref","unstructured":"Blum, M., Luby, M., Rubinfeld, R.: Self-testing\/correcting with applications to numerical problems. Journal of Computer and System Sciences\u00a047, 549\u2013595 (1993) (a preliminary version appeared in Proc. 22 nd STOC, 1990).","DOI":"10.1016\/0022-0000(93)90044-W"},{"key":"28_CR5","doi-asserted-by":"crossref","unstructured":"Fischer, E.: The art of uninformed decisions: A primer to property testing. In: Paun, G., Rozenberg, G., Salomaa, A. (eds.) Current Trends in Theoretical Computer Science: The Challenge of the New Century, vol.\u00a0I, pp. 229\u2013264. World Scientific Publishing (2004)","DOI":"10.1142\/9789812562494_0014"},{"issue":"4","key":"28_CR6","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. JACM\u00a045(4), 653\u2013750 (1998)","journal-title":"JACM"},{"issue":"2","key":"28_CR7","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":"28_CR8","doi-asserted-by":"crossref","unstructured":"Halevy, S., Lachish, O., Newman, I., Tsur, D.: Testing Properties of Constraint-Graphs. In: Halevy, S., Lachish, O., Newman, I., Tsur, D. (eds.) Proceedings of the 22 nd IEEE Annual Conference on Computational Complexity (CCC 2007) (to appear)","DOI":"10.1109\/CCC.2007.31"},{"key":"28_CR9","unstructured":"Halevy, S., Lachish, O., Newman, I., Tsur, D.: Testing Orientation Properties. In: Electronic Colloquium on Computational Complexity (ECCC) (2005)"},{"issue":"6","key":"28_CR10","doi-asserted-by":"publisher","first-page":"1441","DOI":"10.1137\/S0097539703436424","volume":"33","author":"T. Kaufman","year":"2004","unstructured":"Kaufman, T., Krivelevich, M., Ron, D.: Tight bounds for testing bipartiteness in general graphs. SICOMP\u00a033(6), 1441\u20131483 (2004)","journal-title":"SICOMP"},{"issue":"5","key":"28_CR11","doi-asserted-by":"publisher","first-page":"1557","DOI":"10.1137\/S009753970038211X","volume":"31","author":"I. Newman","year":"2002","unstructured":"Newman, I.: Testing Membership in Languages that Have Small Width Branching Programs. SIAM Journal on Computing\u00a031(5), 1557\u20131570 (2002)","journal-title":"SIAM Journal on Computing"},{"issue":"2","key":"28_CR12","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(2), 165\u2013183 (2002)","journal-title":"Random Structures and Algorithms"},{"key":"28_CR13","volume-title":"Handbook of Randomized Computing","author":"D. Ron","year":"2001","unstructured":"Ron, D.: Property testing (a tutorial). In: Pardalos, P.M., Reif, J.H., Rolim, J.D.P. (eds.) Handbook of Randomized Computing, vol.\u00a0II, ch. 15, Kluwer Press, Dordrecht (2001)"},{"key":"28_CR14","unstructured":"Rubinfeld, R., Sudan, M.: Robust characterization of polynomials with applications to program testing. SIAM Journal on Computing\u00a025, 252\u2013271 (1996) (first appeared as a technical report, Cornell University, 1993)."}],"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-540-74208-1_28","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,2]],"date-time":"2019-05-02T16:29:26Z","timestamp":1556814566000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-74208-1_28"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007]]},"ISBN":["9783540742074","9783540742081"],"references-count":14,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-74208-1_28","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2007]]}}}