期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：2002
卷号：2002
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：We consider the problem of testing bipartiteness in the adjacency matrix model. The best known algorithm, due to Alon and Krivelevich, distinguishes between bipartite graphs and graphs that are -far from bipartite using O ((1 2 ) polylo g (1 epsilon ) queries. We show that this is optimal for non-adaptive algorithms, up to the polylogarithmic factor. We also show a lower bound of (1 3 2 ) for adaptive algorithms.
-far from bipartite using O ((1 
