{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T00:22:18Z","timestamp":1725495738609},"publisher-location":"Berlin, Heidelberg","reference-count":33,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540677154"},{"type":"electronic","value":"9783540450221"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2000]]},"DOI":"10.1007\/3-540-45022-x_68","type":"book-chapter","created":{"date-parts":[[2007,11,13]],"date-time":"2007-11-13T18:57:25Z","timestamp":1194980245000},"page":"809-820","source":"Crossref","is-referenced-by-count":7,"title":["Testing Acyclicity of Directed Graphs in Sublinear Time"],"prefix":"10.1007","author":[{"given":"Michael A.","family":"Bender","sequence":"first","affiliation":[]},{"given":"Dana","family":"Ron","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2002,2,18]]},"reference":[{"key":"68_CR1","doi-asserted-by":"crossref","unstructured":"N. Alon, E. Fischer, M. Krivelevich, and M Szegedy. Efficient testing of large graphs. In Proceedings of the Fortieth Annual Symposium on Foundations of Computer Science, pages 656\u2013666, 1999.","DOI":"10.1109\/SFFCS.1999.814642"},{"key":"68_CR2","doi-asserted-by":"crossref","unstructured":"N. Alon, M. Krivelevich, I. Newman, and M Szegedy. Regular languages are testable with a constant number of queries. In Proceedings of the Fortieth Annual Symposium on Foundations of Computer Science, pages 645\u2013655, 1999.","DOI":"10.1109\/SFFCS.1999.814641"},{"key":"68_CR3","doi-asserted-by":"crossref","unstructured":"S. Arora, A. Frieze, and H. Kaplan. A new rounding procedure for the assignment problem with applications to dense graph arrangement problems. In 37th Annual Symposium on Foundations of Computer Science, pages 21\u201330. IEEE, 14\u201316 October 1996.","DOI":"10.1109\/SFCS.1996.548460"},{"key":"68_CR4","doi-asserted-by":"crossref","unstructured":"S. Arora, C. Lund, R. Motwani, M. Sudan, and M. Szegedy. Proof verification and intractability of approximation problems. In Proceedings of the Thirty-Third Annual Symposium on Foundations of Computer Science, pages 14\u201323, 1992.","DOI":"10.1109\/SFCS.1992.267823"},{"key":"68_CR5","doi-asserted-by":"crossref","unstructured":"S. Arora and S. Safra. Probabilistic checkable proofs: A new characterization of NP. In Proceedings of the Thirty-Third Annual Symposium on Foundations of Computer Science, pages 1\u201313, 1992.","DOI":"10.1109\/SFCS.1992.267824"},{"key":"68_CR6","doi-asserted-by":"crossref","unstructured":"L. Babai, L. Fortnow, L. Levin, and M. Szegedy. Checking computations in polylogarithmic time. In Proceedings of the Twenty-Third Annual ACM Symposium on Theory of Computing, pages 21\u201331, 1991.","DOI":"10.1145\/103418.103428"},{"issue":"1","key":"68_CR7","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1007\/BF01200056","volume":"1","author":"L. Babai","year":"1991","unstructured":"L. Babai, L. Fortnow, and C. Lund. Non-deterministic exponential time has two-prover interactive protocols. Computational Complexity, 1(1):3\u201340, 1991.","journal-title":"Computational Complexity"},{"key":"68_CR8","doi-asserted-by":"crossref","unstructured":"M. Bender and D. Ron. Testing acyclicity of directed graphs in sublinear time. Full version of this paper. Available from http:\/\/www.eng.tau.ac.il\/danar , 2000.","DOI":"10.1007\/3-540-45022-X_68"},{"issue":"1","key":"68_CR9","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1006\/jagm.1997.0864","volume":"25","author":"B. Berger","year":"1997","unstructured":"B. Berger and P. W. Shor. Tight bounds for the maximum acyclic subgraph problem. Journal of Algorithms, 25(1):1\u201318, October 1997.","journal-title":"Journal of Algorithms"},{"key":"68_CR10","first-page":"549","volume":"47","author":"M. Blum","year":"1993","unstructured":"M. Blum, M. Luby, and R. Rubinfeld. Self-testing\/correcting with applications to numerical problems. Journal of the Association for Computing Machinery, 47:549\u2013595, 1993.","journal-title":"Journal of the Association for Computing Machinery"},{"key":"68_CR11","doi-asserted-by":"crossref","unstructured":"Y. Dodis, O. Goldreich, E. Lehman, S. Raskhodnikova, D. Ron, and A. Samorodnitsky. Improved testing algorithms for monotonocity. In Proceedings of RANDOM99, 1999.","DOI":"10.1007\/978-3-540-48413-4_10"},{"key":"68_CR12","doi-asserted-by":"crossref","unstructured":"F. Ergun, S. Kannan, S. R. Kumar, R. Rubinfeld, and M. Viswanathan. Spotcheckers. In Proceedings of the Thirty-Second Annual ACM Symposium on the Theory of Computing, pages 259\u2013268, 1998.","DOI":"10.1145\/276698.276757"},{"key":"68_CR13","doi-asserted-by":"crossref","unstructured":"G. Even, J. Naor, B. Schieber, and M. Sudan. Approximating minimum feedback sets and multicuts in directed graphs. Algorithmica, 20, 1998.","DOI":"10.1007\/PL00009191"},{"issue":"2","key":"68_CR14","doi-asserted-by":"crossref","first-page":"268","DOI":"10.1145\/226643.226652","volume":"43","author":"U. Feige","year":"1996","unstructured":"U. Feige, S. Goldwasser, L. Lov\u00e1sz, S. Safra, and M. Szegedy. Approximating clique is almost NP-complete. Journal of the Association for Computing Machinery, 43(2):268\u2013292, 1996.","journal-title":"Journal of the Association for Computing Machinery"},{"key":"68_CR15","unstructured":"A. Frieze and R. Kannan. Quick approximations of matrices. An extended abstract of some of this work appeared in FOCS96 under the title: The Regularity Lemma and approximation schemes for dense problems, 1997."},{"key":"68_CR16","doi-asserted-by":"crossref","unstructured":"P. B. Gibbons and Y. Matias. New sampling-based summary statistics for improving approximate query answers. SIGMOD Record: Proc. ACM SIGMOD Int. Conf. Management of Data, 27(2):331\u2013342, 2\u20134 June 1998.","DOI":"10.1145\/276304.276334"},{"key":"68_CR17","doi-asserted-by":"crossref","unstructured":"P. B. Gibbons and Y. Matias. Synopsis data structures for massive data sets. DI-MACS: Series in Discrete Mathematics and Theoretical Computer Science: Special Issue on External Memory Algorithms and Visualization, A, 1999. to appear.","DOI":"10.1090\/dimacs\/050\/02"},{"key":"68_CR18","doi-asserted-by":"crossref","unstructured":"M. Goemans and D. Williamson. Primal-dual approximation algorithms for feedback problems in planar graphs. Combinatorica, 18, 1998.","DOI":"10.1007\/PL00009810"},{"key":"68_CR19","unstructured":"O. Goldreich, S. Goldwasser, E. Lehman, D. Ron, and A. Samordinsky. Testing monotonicity. To appear in Combinatorica. A preliminary (and weaker) version of this work appeared in FOCS98, 1999."},{"issue":"4","key":"68_CR20","doi-asserted-by":"crossref","first-page":"653","DOI":"10.1145\/285055.285060","volume":"45","author":"O. Goldreich","year":"1998","unstructured":"O. Goldreich, S. Goldwasser, and D. Ron. Property testing and its connection to learning and approximation. Journal of the Association for Computing Machinery, 45(4):653\u2013750, 1998. An extended abstract appeared in FOCS96.","journal-title":"Journal of the Association for Computing Machinery"},{"key":"68_CR21","doi-asserted-by":"crossref","unstructured":"O. Goldreich and D. Ron. Property testing in bounded degree graphs. In Proceedings of the Thirty-First Annual ACM Symposium on the Theory of Computing, pages 406\u2013415, 1997.","DOI":"10.1145\/258533.258627"},{"key":"68_CR22","doi-asserted-by":"crossref","unstructured":"O. Goldreich and D. Ron. A sublinear bipartite tester for bounded degree graphs. In Proceedings of the Thirty-Second Annual ACM Symposium on the Theory of Computing, 1998. To appear in Combinatorica.","DOI":"10.1145\/276698.276767"},{"issue":"3","key":"68_CR23","doi-asserted-by":"crossref","first-page":"133","DOI":"10.1016\/0020-0190(94)00086-7","volume":"51","author":"R. Hassin","year":"1994","unstructured":"R. Hassin and S. Rubinstein. Approximations for the maximum acyclic subgraph problem. Information Processing Letters, 51(3):133\u2013140, August 1994.","journal-title":"Information Processing Letters"},{"issue":"1","key":"68_CR24","doi-asserted-by":"crossref","first-page":"144","DOI":"10.1145\/7531.7535","volume":"34","author":"D. S. Hochbaum","year":"1987","unstructured":"D. S. Hochbaum and D. B. Shmoys. Using dual approximation algorithms for scheduling problems: Theoretical and practical results. Journal of the Association for Computing Machinery, 34(1):144\u2013162, January 1987.","journal-title":"Journal of the Association for Computing Machinery"},{"issue":"3","key":"68_CR25","doi-asserted-by":"publisher","first-page":"539","DOI":"10.1137\/0217033","volume":"17","author":"D. S. Hochbaum","year":"1988","unstructured":"D. S. Hochbaum and D. B. Shmoys. A polynomial approximation scheme for machine scheduling on uniform processors: Using the dual approximation approach. SI AM Journal on Computing, 17(3):539\u2013551, 1988.","journal-title":"SI AM Journal on Computing"},{"key":"68_CR26","series-title":"PhD thesis","volume-title":"On the Approximability of NP-Complete Optimization Problems","author":"V. Kann","year":"1992","unstructured":"V. Kann. On the Approximability of NP-Complete Optimization Problems. PhD thesis, Department of Numberical Analysis and Computer Science, Royal Institute of Technology, Stockholm, 1992."},{"key":"68_CR27","doi-asserted-by":"crossref","unstructured":"R. M. Karp. Reducibility among combinatorial problems. In R. E. Miller and J. W. Thatcher, editors, Complexity of Computer Computations, pages 85\u2013103, New York, 1972. Plenum Press.","DOI":"10.1007\/978-1-4684-2001-2_9"},{"key":"68_CR28","doi-asserted-by":"crossref","unstructured":"M. Kearns and D. Ron. Testing problems with sub-learning sample complexity. In Proceedings of the Eleventh Annual ACM Conference on Computational Learning Theory, pages 268\u2013277, 1998.","DOI":"10.1145\/279943.279996"},{"key":"68_CR29","doi-asserted-by":"publisher","first-page":"425","DOI":"10.1016\/0022-0000(91)90023-X","volume":"43","author":"C. Papadimitriou","year":"1991","unstructured":"C. Papadimitriou and M. Yannakakis. Optimization, approximization and complexity classes. Journal of Computer and System Sciences, 43:425\u2013440, 1991.","journal-title":"Journal of Computer and System Sciences"},{"key":"68_CR30","doi-asserted-by":"crossref","unstructured":"M. Parnas and D. Ron. Testing the diameter of graphs. In Proceedings of Random99, pages 85\u201396, 1999.","DOI":"10.1007\/978-3-540-48413-4_9"},{"key":"68_CR31","doi-asserted-by":"crossref","unstructured":"R. Rubinfeld. Robust functional equations and their applications to program testing. In Proceedings of the Thirty-Fifth Annual Symposium on Foundations of Computer Science, 1994.","DOI":"10.1109\/SFCS.1994.365686"},{"issue":"2","key":"68_CR32","doi-asserted-by":"publisher","first-page":"252","DOI":"10.1137\/S0097539793255151","volume":"25","author":"R. Rubinfeld","year":"1996","unstructured":"R. Rubinfeld and M. Sudan. Robust characterization of polynomials with applications to program testing. SIAM Journal on Computing, 25(2):252\u2013271, 1996.","journal-title":"SIAM Journal on Computing"},{"key":"68_CR33","doi-asserted-by":"crossref","unstructured":"P. D. Seymour. Packing directed circuits fractionally. Combinatorica, 15, 1995.","DOI":"10.1007\/BF01200760"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-45022-X_68","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,4]],"date-time":"2019-05-04T07:25:22Z","timestamp":1556954722000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-45022-X_68"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2000]]},"ISBN":["9783540677154","9783540450221"],"references-count":33,"URL":"https:\/\/doi.org\/10.1007\/3-540-45022-x_68","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2000]]}}}