Fast computation of small cuts via cycle space sampling
Fast computation of small cuts via cycle space sampling
复制标题
通过循环空间采样快速计算小切口
DOI：
--
复制
发表时间：
2007
期刊：
影响因子：
--
通讯作者：
R. Thurimella
中科院分区：
文献类型：
--
作者：
David Pritchard;R. Thurimella
我们描述了一种新的基于采样的方法来确定无向图中的切割。对于图（<i>V</i>，<i>E</i>），其循环空间是在每个顶点具有偶数度的 <i>E</i> 的所有子集的族。我们证明，对循环空间进行采样可以以很高的概率识别出图的割点。这导致了简单的新线性时间顺序算法，用于查找图的所有切割边和切割对（形成切割的一组 2 条边）。
在具有 <i>O</i>(log |<i>V</i>|) 位消息的图 <i>G</i> = (<i>V</i>, <i>E</i>) 的分布式计算模型中，我们的方法为多个问题提供了更快的算法。 <i>G</i>的直径用<i>D</i>表示，最大度数用Δ表示。我们获得简单的<i>O</i>(<i>D</i>)时间分布式算法来查找所有切割边、2边连接的分量和切割对，匹配或改进先前的时间界限。在自然条件下，这些新算法是普遍最优的，即每个图都存在 Ω(<i>D</i>) 时间下界。我们得到了一个<i>O</i>(<i>D</i>+Δ/log |V|)时间的分布式算法来寻找割点；当 Δ, <i>D</i> = <i>O</i>(&sqrt;|<i>V</i>|) 时，这比之前最好的算法更快。我们工作的简单扩展产生了第一个针对 3 边连接组件具有亚线性时间的分布式算法。基本的分布式算法是蒙特卡罗，但它们可以在不增加渐近复杂度的情况下做成拉斯维加斯。
在 EREW PRAM 上的并行计算模型中，我们的方法产生了一种具有最佳时间复杂度 <i>O</i>(log <i>V</i>) 的简单算法，用于查找切割对和 3 边连接组件。
We describe a new sampling-based method to determine cuts in an undirected graph. For a graph (<i>V</i>, <i>E</i>), its cycle space is the family of all subsets of <i>E</i> that have even degree at each vertex. We prove that with high probability, sampling the cycle space identifies the cuts of a graph. This leads to simple new linear-time sequential algorithms for finding all cut edges and cut pairs (a set of 2 edges that form a cut) of a graph.
In the model of distributed computing in a graph <i>G</i> = (<i>V</i>, <i>E</i>) with <i>O</i>(log |<i>V</i>|)-bit messages, our approach yields faster algorithms for several problems. The diameter of <i>G</i> is denoted by <i>D</i>, and the maximum degree by Δ. We obtain simple <i>O</i>(<i>D</i>)-time distributed algorithms to find all cut edges, 2-edge-connected components, and cut pairs, matching or improving upon previous time bounds. Under natural conditions these new algorithms are universally optimal—that is, a Ω(<i>D</i>)-time lower bound holds on every graph. We obtain a <i>O</i>(<i>D</i>+Δ/log |V|)-time distributed algorithm for finding cut vertices; this is faster than the best previous algorithm when Δ, <i>D</i> = <i>O</i>(&sqrt;|<i>V</i>|). A simple extension of our work yields the first distributed algorithm with sub-linear time for 3-edge-connected components. The basic distributed algorithms are Monte Carlo, but they can be made Las Vegas without increasing the asymptotic complexity.
In the model of parallel computing on the EREW PRAM, our approach yields a simple algorithm with optimal time complexity <i>O</i>(log <i>V</i>) for finding cut pairs and 3-edge-connected components.