Planar Graphs: Random Walks and Bipartiteness Testing
Planar Graphs: Random Walks and Bipartiteness Testing
复制标题
平面图：随机游走和二分测试
DOI：
10.1109/focs.2011.69
复制
发表时间：
2011
期刊：
影响因子：
--
通讯作者：
Czumaj A
中科院分区：
文献类型：
--
作者：
Czumaj A
本文首先研究了任意平面图的性质的可测性。我们证明了二分性可以在常数时间内检验。这类图的上界是O（n），而常数时间可测性只存在于度有界的平面图中。以前使用的无界度稀疏图到有界度稀疏图的变换不能用于将问题减少到有界度平面图的可测性。我们的方法扩展到任意小自由图。我们的算法是基于随机游动。这里的挑战是分析一类具有良好分隔符的图的随机游动，即，不良扩张使用快速收敛到均匀分布的标准技术在这种情况下不起作用。粗略地说，我们的分析技术将在由一组圈诱导的多重图G中找到一个奇长圈的问题自简化为由一组较短的奇长圈诱导的另一个多重图G'，以这种方式，当随机游动以概率p >; 0在G'中找到一个圈时，它在G中的概率λ（p）>; 0。应用这种减少直到循环崩溃为可以容易地检测到的自循环。
We initiate the study of the testability of properties in arbitrary planar graphs. We prove that bipartiteness can be tested in constant time. The previous bound for this class of graphs was O(√n), and the constant-time testability was only known for planar graphs with bounded degree. Previously used transformations of unbounded-degree sparse graphs into bounded- degree sparse graphs cannot be used to reduce the problem to the testability of bounded-degree planar graphs. Our approach extends to arbitrary minor-free graphs. Our algorithm is based on random walks. The challenge here is to analyze random walks for a class of graphs that has good separators, i.e., bad expansion. Standard techniques that use a fast convergence to a uniform distribution do not work in this case. Roughly speaking, our analysis technique self-reduces the problem of finding an odd-length cycle in a multigraph G induced by a collection of cycles to another multigraph G' induced by a set of shorter odd-length cycles, in such a way that when a random walks finds a cycle in G' with probability p >; 0, then it does so with probability λ(p) >; 0 in G. This reduction is applied until the cycles collapse to self-loops that can be easily detected.
登录
查看更多内容
稀疏图的每个小闭性质都是可测试的
DOI：
10.1145/1374376.1374433
发表时间：
2008
期刊：
Proceedings of the fortieth annual ACM symposium on Theory of computing
影响因子：
--
作者：
I. Benjamini;O. Schramm;A. Shapira
通讯作者：
A. Shapira
测试有界度图中的扩展
DOI：
--
发表时间：
2007
期刊：
IEEE Annual Symposium on Foundations of Computer Science
影响因子：
--
作者：
A. Czumaj;C. Sohler
通讯作者：
C. Sohler
近似有界度和一般稀疏图中属性的距离
DOI：
10.1145/1497290.1497298
发表时间：
2009
期刊：
ACM Trans. Algorithms
影响因子：
--
作者：
S. Marko;D. Ron
通讯作者：
D. Ron
DOI：
10.1007/978-3-540-45198-3_29
发表时间：
2004
期刊：
SIAM J. Comput.
影响因子：
--
作者：
T. Kaufman;Michael Krivelevich;D. Ron
通讯作者：
D. Ron
影响因子：
1
作者：
Michal Parnas;D. Ron
通讯作者：
D. Ron