{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T22:08:30Z","timestamp":1725574110166},"publisher-location":"Berlin, Heidelberg","reference-count":17,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540407706"},{"type":"electronic","value":"9783540451983"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2003]]},"DOI":"10.1007\/978-3-540-45198-3_29","type":"book-chapter","created":{"date-parts":[[2011,1,8]],"date-time":"2011-01-08T03:32:30Z","timestamp":1294457550000},"page":"341-353","source":"Crossref","is-referenced-by-count":6,"title":["Tight Bounds for Testing Bipartiteness in General Graphs"],"prefix":"10.1007","author":[{"given":"Tali","family":"Kaufman","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Michael","family":"Krivelevich","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Dana","family":"Ron","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"29_CR1","doi-asserted-by":"publisher","first-page":"359","DOI":"10.1002\/rsa.10056","volume":"21","author":"N. Alon","year":"2002","unstructured":"Alon, N.: Testing subgraphs of large graphs. Random Structures and Algorithms\u00a021, 359\u2013370 (2002)","journal-title":"Random Structures and Algorithms"},{"key":"29_CR2","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, 451\u2013476 (2000)","journal-title":"Combinatorica"},{"issue":"2","key":"29_CR3","doi-asserted-by":"publisher","first-page":"211","DOI":"10.1137\/S0895480199358655","volume":"15","author":"N. Alon","year":"2002","unstructured":"Alon, N., Krivelevich, M.: Testing k-colorability. SIAM Journal on Discrete Math\u00a015(2), 211\u2013227 (2002)","journal-title":"SIAM Journal on Discrete Math"},{"key":"29_CR4","doi-asserted-by":"crossref","unstructured":"Alon, N., Shapira, A.: Testing subgraph in directed graphs (2002) (submitted)","DOI":"10.1145\/780542.780644"},{"key":"29_CR5","doi-asserted-by":"crossref","unstructured":"Bender, M., Ron, D.: Testing properties of directed graphs: Acyclicity and connectivity. Random Structures and Algorithms, 184\u2013205 (2002)","DOI":"10.1002\/rsa.10023"},{"key":"29_CR6","doi-asserted-by":"crossref","unstructured":"Bogdanov, A., Obata, K., Trevisan, L.: A lower bound for testing 3-colorability in bounded-degree graphs. In: Proceedings of the Forty-Third Annual Symposium on Foundations of Computer Science, pp. 93\u2013102 (2002)","DOI":"10.1109\/SFCS.2002.1181886"},{"key":"29_CR7","unstructured":"Bogdanov, A., Trevisan, L.: Lower bounds for testing bipartiteness in dense graphs (2002) (submitted)"},{"key":"29_CR8","doi-asserted-by":"crossref","unstructured":"Goldreich, O., Goldwasser, S., Ron, D.: Property testing and its connection to learning and approximation. In: Proceedings of the Thirty-Seventh Annual Symposium on Foundations of Computer Science, pp. 339\u2013348 (1996)","DOI":"10.1109\/SFCS.1996.548493"},{"issue":"3","key":"29_CR9","doi-asserted-by":"publisher","first-page":"335","DOI":"10.1007\/s004930050060","volume":"19","author":"O. Goldreich","year":"1999","unstructured":"Goldreich, O., Ron, D.: A sublinear bipartite tester for bounded degree graphs. Combinatorica\u00a019(3), 335\u2013373 (1999)","journal-title":"Combinatorica"},{"key":"29_CR10","doi-asserted-by":"crossref","unstructured":"Goldreich, O., Ron, D.: Property testing in bounded degree graphs. Algorithmica, 302\u2013343 (2002)","DOI":"10.1007\/s00453-001-0078-7"},{"key":"29_CR11","doi-asserted-by":"crossref","unstructured":"Goldreich, O., Trevisan, L.: Three theorems regarding testing graph properties. In: Proceedings of the Forty-Second Annual Symposium on Foundations of Computer Science, pp. 460\u2013469 (2001)","DOI":"10.1109\/SFCS.2001.959922"},{"key":"29_CR12","unstructured":"Kaufman, T., Krivelevich, M., Ron, D.: Tight bounds for testing bipartiteness in general graphs, http:\/\/www.eng.tau.ac.il\/~danar\/papers.html"},{"key":"29_CR13","doi-asserted-by":"crossref","unstructured":"Lubotzky, A., Phillips, R., Sarnak, P.: Explicit expanders and the ramanujan conjectures. In: Proceedings of the Eighteenth Annual ACM Symposium on Theory of Computing, pp. 240\u2013246 (1986)","DOI":"10.1145\/12130.12154"},{"issue":"4","key":"29_CR14","first-page":"71","volume":"9","author":"G.A. Margulis","year":"1973","unstructured":"Margulis, G.A.: Explicit constructions of expanders. Problemy Peredachi Informatsii\u00a09(4), 71\u201380 (1973) (expanders construction)","journal-title":"Problemy Peredachi Informatsii"},{"issue":"2","key":"29_CR15","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"},{"issue":"2","key":"29_CR16","doi-asserted-by":"publisher","first-page":"252","DOI":"10.1137\/S0097539793255151","volume":"25","author":"R. Rubinfeld","year":"1996","unstructured":"Rubinfeld, R., Sudan, M.: Robust characterization of polynomials with applications to program testing. SIAM Journal on Computing\u00a025(2), 252\u2013271 (1996)","journal-title":"SIAM Journal on Computing"},{"key":"29_CR17","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":["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-45198-3_29","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,6,7]],"date-time":"2019-06-07T18:05:14Z","timestamp":1559930714000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-45198-3_29"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2003]]},"ISBN":["9783540407706","9783540451983"],"references-count":17,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-45198-3_29","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2003]]}}}