Cole, Richard ; Hariharan, Ramesh (2003) A fast algorithm for computing steiner edge connectivity In: STOC '03 Proceedings of the Thirty-Fifth Annual ACM Symposium on Theory of Computing, June 09-11, 2003, San Diego, CA, USA.
Full text not available from this repository.
Official URL: http://dl.acm.org/citation.cfm?id=780542.780568
Abstract
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.
Item Type: | Conference or Workshop Item (Paper) |
---|---|
Source: | Copyright of this article belongs to ACM, Inc. |
ID Code: | 102347 |
Deposited On: | 09 Mar 2018 11:24 |
Last Modified: | 09 Mar 2018 11:24 |
Repository Staff Only: item control page