A fast algorithm for optimally increasing the edge-connectivity
A fast algorithm for optimally increasing the edge-connectivity
复制标题
一种最佳地增加边缘连通性的快速算法
DOI：
10.1109/fscs.1990.89592
复制
发表时间：
1990
期刊：
影响因子：
--
通讯作者：
C. Martel
中科院分区：
文献类型：
--
作者：
D. Naor;D. Gusfield;C. Martel
考虑了一个未方向的，未加权的图G =（v，e带N节点，m边缘和连接lambda）。给定输入参数增量，边缘增强问题是找到要添加到G中的最小边缘，以使其边缘连接性增加了Delta。在时间O（Delta /sup 2 /nm+nf（n））中运行的该问题的解决方案，其中F（n）是在G上执行最大流量的时间。该解决方案给出了每个delta'，1 <or = delta'<或= delta的最佳增强。解决方案的修改可以解决问题，而无需事先知道三角洲。如果delta = 1，则解决方案特别简单，在O（nm）时间内运行，并且是K. Eswaran和R.E.的算法的自然概括。 Tarjan（1976）对于Lambda + Delta = 2的情况。相反的问题（给定输入号k，通过在最多k边缘添加来提高G的连接性）在同一时间绑定。该解决方案广泛使用了特定剪切组的结构。<< etx >>
An undirected, unweighted graph G=(V, E with n nodes, m edges, and connectivity lambda ) is considered. Given an input parameter delta , the edge augmentation problem is to find the smallest set of edges to add to G so that its edge-connectivity is increased by delta . A solution to this problem that runs in time O( delta /sup 2/nm+nF(n)), where F(n) is the time to perform one maximum flow on G, is given. The solution gives the optimal augmentation for every delta ', 1<or= delta '<or= delta , in the same time bound. A modification of the solution solves the problem without knowing delta in advance. If delta =1, then the solution is particularly simple, running in O(nm) time, and it is a natural generalization of an algorithm of K. Eswaran and R.E. Tarjan (1976) for the case in which lambda + delta =2. The converse problem (given an input number k, increase the connectivity of G as much as possible by adding at most k edges) is solved in the same time bound. The solution makes extensive use of the structure of particular sets of cuts.<<ETX>>