{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T06:32:03Z","timestamp":1725517923572},"publisher-location":"Berlin, Heidelberg","reference-count":26,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540853626"},{"type":"electronic","value":"9783540853633"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/978-3-540-85363-3_32","type":"book-chapter","created":{"date-parts":[[2008,8,27]],"date-time":"2008-08-27T15:29:28Z","timestamp":1219850968000},"page":"402-415","source":"Crossref","is-referenced-by-count":6,"title":["On the Query Complexity of Testing Orientations for Being Eulerian"],"prefix":"10.1007","author":[{"given":"Eldar","family":"Fischer","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Oded","family":"Lachish","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ilan","family":"Newman","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Arie","family":"Matsliah","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Orly","family":"Yahalom","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"3","key":"32_CR1","doi-asserted-by":"publisher","first-page":"354","DOI":"10.1016\/j.jcss.2004.04.008","volume":"69","author":"N. Alon","year":"2004","unstructured":"Alon, N., Shapira, A.: Testing subgraphs in directed graphs. J. Comput. Syst. Sci.\u00a069(3), 354\u2013382 (2004) (a preliminary version appeared in Proc. of STOC 2003, pp. 700-709)","journal-title":"J. Comput. Syst. Sci."},{"doi-asserted-by":"crossref","unstructured":"Babai, L.: On the diameter of Eulerian orientations of graphs. In: Proceedings of the 17\n                    th\n                   SODA, pp. 822\u2013831 (2006)","key":"32_CR2","DOI":"10.1145\/1109557.1109648"},{"doi-asserted-by":"crossref","unstructured":"Bender, M., Ron, D.: Testing properties of directed graphs: Acyclicity and connectivity. Random Structures and Algorithms, 184\u2013205 (2002)","key":"32_CR3","DOI":"10.1002\/rsa.10023"},{"issue":"1","key":"32_CR4","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1137\/S0097539704445445","volume":"35","author":"E. Ben-Sasson","year":"2003","unstructured":"Ben-Sasson, E., Harsha, P., Raskhodnikova, S.: Some 3CNF properties are hard to test. SIAM J. Computing\u00a035(1), 1\u201321 (2005) (a preliminary version appeared in Proc.35\n                    th\n                   STOC, 2003)","journal-title":"SIAM J. Computing"},{"key":"32_CR5","doi-asserted-by":"publisher","first-page":"549","DOI":"10.1016\/0022-0000(93)90044-W","volume":"47","author":"M. Blum","year":"1993","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\n                    nd\n                   STOC, 1990)","journal-title":"Journal of Computer and System Sciences"},{"key":"32_CR6","first-page":"259","volume-title":"Proc. 7th ALENEX and 2nd ANALCO 2005 (Vancouver BC)","author":"G.R. Brightwell","year":"2005","unstructured":"Brightwell, G.R., Winkler, P.: Counting Eulerian circuits is #P-complete. In: Demetrescu, C., Sedgewick, R., Tamassia, R. (eds.) Proc. 7th ALENEX and 2nd ANALCO 2005 (Vancouver BC), pp. 259\u2013262. SIAM Press, Demetrescu (2005)"},{"doi-asserted-by":"crossref","unstructured":"Chakraborty, S., Fischer, E., Lachish, O., Matsliah, A., Newman, I.: Testing st-Connectivity. In: Proceedings of the 11\n                    th\n                   RANDOM and the 10\n                    th\n                   APPROX, pp. 380\u2013394 (2007)","key":"32_CR7","DOI":"10.1007\/978-3-540-74208-1_28"},{"key":"32_CR8","doi-asserted-by":"crossref","first-page":"229","DOI":"10.1142\/9789812562494_0014","volume-title":"Current Trends in Theoretical Computer Science: The Challenge of the New Century","author":"E. Fischer","year":"2004","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, Singapore (2004)"},{"key":"32_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"109","DOI":"10.1007\/978-3-540-70918-3_10","volume-title":"STACS 2007","author":"E. Fischer","year":"2007","unstructured":"Fischer, E., Yahalom, O.: Testing convexity properties of tree colorings. In: Thomas, W., Weil, P. (eds.) STACS 2007. LNCS, vol.\u00a04393, pp. 109\u2013120. Springer, Heidelberg (2007)"},{"unstructured":"Fleishcner, H.: Eulerian graphs and related topics, Part 1. Vol. 1. Annals of Discrete Mathematics\u00a045 (1990)","key":"32_CR10"},{"unstructured":"Fleishcner, H.: Eulerian graphs and related topics, Part 1. Vol. 2. Annals of Discrete Mathematics\u00a050 (1991)","key":"32_CR11"},{"issue":"4","key":"32_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. JACM\u00a045(4), 653\u2013750 (1998)","journal-title":"JACM"},{"issue":"2","key":"32_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\u00a032(2), 302\u2013343 (2002)","journal-title":"Algorithmica"},{"doi-asserted-by":"crossref","unstructured":"Halevy, S., Lachish, O., Newman, I., Tsur, D.: Testing properties of constraint-graphs. In: Proceedings of the 22\n                    nd\n                   IEEE Annual Conference on Computational Complexity (CCC 2007), pp. 264\u2013277 (2007)","key":"32_CR14","DOI":"10.1109\/CCC.2007.31"},{"unstructured":"Halevy, S., Lachish, O., Newman, I., Tsur, D.: Testing orientation properties, technical report, Electronic Colloquium on Computational Complexity (ECCC), 153 (2005)","key":"32_CR15"},{"issue":"1","key":"32_CR16","doi-asserted-by":"publisher","first-page":"61","DOI":"10.1007\/PL00009811","volume":"18","author":"T. Ibaraki","year":"1988","unstructured":"Ibaraki, T., Karzanov, A.V., Nagamochi, H.: A fast algorithm for finding a maximum free multiflow in an inner Eulerian network and some generalizations. Combinatorica\u00a018(1), 61\u201383 (1988)","journal-title":"Combinatorica"},{"issue":"6","key":"32_CR17","doi-asserted-by":"crossref","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"},{"key":"32_CR18","doi-asserted-by":"publisher","first-page":"129","DOI":"10.1007\/BF01902503","volume":"28","author":"L. Lov\u00e1sz","year":"1976","unstructured":"Lov\u00e1sz, L.: On some connectivity properties of Eulerian graphs. Acta Math. Hung.\u00a028, 129\u2013138 (1976)","journal-title":"Acta Math. Hung."},{"issue":"4\/5","key":"32_CR19","doi-asserted-by":"crossref","first-page":"402","DOI":"10.1007\/BF01940872","volume":"16","author":"M. Mihail","year":"1996","unstructured":"Mihail, M., Winkler, P.: On the number of Eulerian orientations of a graph. Algorithmica\u00a016(4\/5), 402\u2013414 (1996)","journal-title":"Algorithmica"},{"issue":"5","key":"32_CR20","doi-asserted-by":"publisher","first-page":"1557","DOI":"10.1137\/S009753970038211X","volume":"31","author":"I. Newman","year":"2002","unstructured":"Newman, I.: Testing of Functions that have small width Branching Programs. SIAM J. Computing\u00a031(5), 1557\u20131570 (2002) (a preliminary version appeared in Proc. 41\n                    st\n                   FOCS, 2000)","journal-title":"SIAM J. Computing"},{"issue":"2","key":"32_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. and Algorithms\u00a020(2), 165\u2013183 (2002)","journal-title":"Random Struct. and Algorithms"},{"key":"32_CR22","doi-asserted-by":"publisher","first-page":"9748","DOI":"10.1073\/pnas.171285098","volume":"98","author":"P.A. Pevzner","year":"2001","unstructured":"Pevzner, P.A., Tang, H., Waterman, M.S.: An Eulerian path approach to DNA fragment assembly. Proc. Natl. Acad. Sci. USA\u00a098, 9748\u20139753 (2001)","journal-title":"Proc. Natl. Acad. Sci. USA"},{"key":"32_CR23","first-page":"147","volume-title":"Proof Techniques in Graph Theory","author":"R.W. Robinson","year":"1969","unstructured":"Robinson, R.W.: Enumeration of Euler graphs. In: Harary, F. (ed.) Proof Techniques in Graph Theory, pp. 147\u2013153. Academic Press, New York (1969)"},{"key":"32_CR24","volume-title":"Handbook of Randomized Computing","author":"D. Ron","year":"2001","unstructured":"Ron, D.: Property testing (a tutorial). In: Rajasekaran, S., Pardalos, P.M., Reif, J.H., Rolim, J.D.P. (eds.) Handbook of Randomized Computing, vol.\u00a0II, ch.15. Kluwer Press, Dordrecht (2001)"},{"key":"32_CR25","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 J. Computing\u00a025, 252\u2013271 (1996) (first appeared as a technical report, Cornell University, 1993)","journal-title":"SIAM J. Computing"},{"key":"32_CR26","volume-title":"Graph theory","author":"W.T. Tutte","year":"1984","unstructured":"Tutte, W.T.: Graph theory. Addison-Wesley, New York (1984)"}],"container-title":["Lecture Notes in Computer Science","Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-85363-3_32.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T07:35:10Z","timestamp":1619508910000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-85363-3_32"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["9783540853626","9783540853633"],"references-count":26,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-85363-3_32","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[]}}