Large Cuts with Local Algorithms on Triangle-Free Graphs
Large Cuts with Local Algorithms on Triangle-Free Graphs
复制标题
在无三角形图上使用局部算法进行大切割
DOI：
--
复制
发表时间：
2014
影响因子：
0.7
通讯作者：
J. Suomela
中科院分区：
文献类型：
--
作者：
J. Hirvonen;Joel Rybicki;S. Schmid;J. Suomela
我们研究在$d$-正则无三角形图中寻找大切口的问题。在之前的工作中，Shearer (1992) 给出了一种随机算法，可以找到预期大小 $(1/2 + 0.177/sqrt{d})m$ 的切割，其中 $m$ 是边数。我们给出了一个更简单、效果更好的算法：它找到预期大小 $(1/2 + 0.28125/sqrt{d})m$ 的切割。作为推论，这表明在任何$d$-正则无三角形图中，都存在至少这个大小的切割。
我们的算法可以解释为一种非常高效的随机分布式算法：每个节点只需要产生一个随机位，并且该算法在一个同步通信轮中运行。这项工作也是在分布式算法设计中应用计算技术的案例研究：我们的算法是由一个计算机程序设计的，该程序搜索 $d$ 小值的最佳算法。
We study the problem of finding large cuts in $d$-regular triangle-free graphs. In prior work, Shearer (1992) gives a randomised algorithm that finds a cut of expected size $(1/2 + 0.177/sqrt{d})m$, where $m$ is the number of edges. We give a simpler algorithm that does much better: it finds a cut of expected size $(1/2 + 0.28125/sqrt{d})m$. As a corollary, this shows that in any $d$-regular triangle-free graph there exists a cut of at least this size.
Our algorithm can be interpreted as a very efficient randomised distributed algorithm: each node needs to produce only one random bit, and the algorithm runs in one synchronous communication round. This work is also a case study of applying computational techniques in the design of distributed algorithms: our algorithm was designed by a computer program that searched for optimal algorithms for small values of $d$.