Tight Bounds for Testing Bipartiteness in General Graphs
Tight Bounds for Testing Bipartiteness in General Graphs
复制标题
测试一般图中二部性的紧界
DOI：
10.1007/978-3-540-45198-3_29
复制
发表时间：
2004
期刊：
影响因子：
--
通讯作者：
D. Ron
中科院分区：
文献类型：
--
作者：
T. Kaufman;Michael Krivelevich;D. Ron
在本文中，我们考虑了一般图的两性问题的问题。具有恒定复杂性的两性性，而测试有限度图的复杂性是θ？（√n），n在图中的顶点数量是n。在这项工作中，我们尤其是在上面描述的差距。 m））其中m是图中的边数，并与几乎紧密的下限匹配。
In this paper we consider the problem of testing bipartiteness of general graphs. The problem has previously been studied in two models, one most suitable for dense graphs, and one most suitable for bounded-degree graphs. Roughly speaking, dense graphs can be tested for bipartiteness with constant complexity, while the complexity of testing bounded-degree graphs is θ?(√n), where n is the number of vertices in the graph. Thus there is a large gap between the complexity of testing in the two cases. In this work we bridge the gap described above. In particular, we study the problem of testing bipartiteness in a model that is suitable for all densities. We present an algorithm whose complexity is O(min(√n, n 2 /m)) where m is the number of edges in the graph, and match it with an almost tight lower bound.