A fast algorithm for computing steiner edge connectivity
A fast algorithm for computing steiner edge connectivity
复制标题
计算斯坦纳边缘连通性的快速算法
DOI：
10.1145/780542.780568
复制
发表时间：
2003
期刊：
影响因子：
2.1
通讯作者：
R. Hariharan
中科院分区：
文献类型：
--
作者：
R. Cole;R. Hariharan
给定一个无向图或欧拉有向图G及其顶点子集S，我们给出了如何确定S中顶点在时间O（C3 nlogn +m）内的边连通度C.该算法是基于一个有效的构造树包装推广埃德蒙兹定理。这些包装也产生的所有最小Steiner切割的大小C的一个有效的数据结构，用于保持边插入下的S中的顶点之间的连接，可以得到一个表征。这种数据结构使得能够有效地构造仙人掌树，用于在相同的时间范围内表示这些顶点之间的显著C-割，称为C-分离。反过来，我们使用仙人掌树给出了一个快速实现的近似算法的生存网络设计问题，由于威廉姆森，Goemans，Mihail和Vazirani。
Given an undirected graph or an Eulerian directed graph G and a subset S of its vertices, we show how to determine the edge connectivity C of the vertices in S in time O(C3 n log n+m). This algorithm is based on an efficient construction of tree packings which generalizes Edmonds' Theorem. These packings also yield a characterization of all minimal Steiner cuts of size C from which an efficient data structure for maintaining edge connectivity between vertices in S under edge insertion can be obtained. This data structure enables the efficient construction of a cactus tree for representing significant C-cuts among these vertices, called C-separations, in the same time bound. In turn, we use the cactus tree to give a fast implementation of an approximation algorithm for the Survivable Network Design problem due to Williamson, Goemans, Mihail and Vazirani.