Computing vertex connectivity: new bounds from old techniques
Computing vertex connectivity: new bounds from old techniques
复制标题
DOI：
10.1109/sfcs.1996.548505
复制
发表时间：
1996-10
期刊：
影响因子：
--
通讯作者：
Monika Henzinger;Satish Rao;H. Gabow
中科院分区：
文献类型：
--
作者：
Monika Henzinger;Satish Rao;H. Gabow
图的顶点连通性 /spl kappa/ 是最小数量的顶点，其删除会使图分离或使其变得微不足道。我们提出了已知最快的确定性算法来查找顶点连通性和相应的分隔符。具有 n 个顶点和 m 个边的有向图的时间为 O(min{/spl kappa//sup 3/+n,/spl kappa/n}m)；对于无向图，术语 m 可以替换为 /spl kappa/n。随机算法在时间 O(nm) 内以 1/2 的错误概率找到 /spl kappa/。如果顶点具有非负权重，则在时间 O(/spl kappa//sub 1/nmlog(n/sup 2//m)) 中找到加权顶点连通性，其中 /spl kappa//sub 1//spl les/m/n 是未加权顶点连通性，或者在预期时间 O(nm log(n/sup 2//m)) 中找到，错误概率为 1/2。主要算法结合了之前的两种顶点连通性算法和 J.Hao 和 J.B.Orlin (1994) 计算边缘连通性的预流推送算法的推广。
The vertex connectivity /spl kappa/ of a graph is the smallest number of vertices whose deletion separates the graph or makes it trivial. We present the fastest known deterministic algorithm for finding the vertex connectivity and a corresponding separator. The time for a digraph having n vertices and m edges is O(min{/spl kappa//sup 3/+n,/spl kappa/n}m); for an undirected graph the term m can be replaced by /spl kappa/n. A randomized algorithm finds /spl kappa/ with error probability 1/2 in time O(nm). If the vertices have nonnegative weights the weighted vertex connectivity is found in time O(/spl kappa//sub 1/nmlog(n/sup 2//m)) where /spl kappa//sub 1//spl les/m/n is the unweighted vertex connectivity, or in expected time O(nm log(n/sup 2//m)) with error probability 1/2. The main algorithm combines two previous vertex connectivity algorithms and a generalization of the preflow push algorithm of J. Hao and J.B. Orlin (1994) that computes edge connectivity.