A Static 2-Approximation Algorithm for Vertex Connectivity and Incremental Approximation Algorithms for Edge and Vertex Connectivity

This paper presents insertions-only algorithms for maintaining the exact and/or approximate size of the minimum edge cut and the minimum vertex cut of a graph. The algorithms output the approximate or exact size k in time O(1) and a cut of size K in time linear in its size. For the minimum edge cut problem and for any O < E <= 1, the amortized time per insertion is O(1/pow2(E))for a (2 + E)-approximation, O((log L)((log n)/E)2) for a (1 + E)-approximation, and O(L log n) for the exact size, where n is the number of nodes in the graph and L is the size of the minimum cut. The (2 + E)-approximation algorithm and the exact algorithm are deterministic; the (1 + E)-approximation algorithm is randomized. We also present a static 2-approximation algorithm for the size K of the minimum vertex cut in a graph, which takes time O(n2 min(Vn , K)). This is a factor of K faster than the best algorithm for computing the exact size, which takes time O((pow3(K)n + K.pow2(n))min(Vn, K)). We give an insertions-only algorithm for maintaining a (2 + E)-approximation of the minimum vertex cut with amortized insertion time O(n/E).

Published in:
J Algorithms, 24, 1, 194-220
Other identifiers:
Scopus: 2-s2.0-0346581426

 Record created 2007-01-18, last modified 2018-03-17

Rate this document:

Rate this document:
(Not yet reviewed)