Mr. Henzinger, A STATIC 2-APPROXIMATION ALGORITHM FOR VERTEX CONNECTIVITY AND INCREMENTAL APPROXIMATION ALGORITHMS FOR EDGE AND VERTEX CONNECTIVITY, Journal of algorithms, 24(1), 1997, pp. 194-220
Citations number
23
Categorie Soggetti
Mathematics,Mathematics,"Computer Science Theory & Methods
This paper presents insertions-only algorithms for maintaining the exa
ct and/or approximate size of the minimum edge cut and the minimum ver
tex cut of a graph. The algorithms output the approximate or exact siz
e k in time O(1) and a cut of size k in time linear in its size. For t
he minimum edge cut problem and for any 0 < epsilon less than or equal
to 1, the amortized time per insertion is O(1/epsilon(2)) for a (2 epsilon)-approximation, O((log lambda)((log n)/epsilon)(2)) for a (1 epsilon)-approximation, and O(lambda log n) for the exact size, where
n is the number of nodes in the graph and lambda is the size of the m
inimum cut. The (2 + epsilon)-approximation algorithm and the exact al
gorithm are deterministic; the (1 + epsilon)-approximation algorithm i
s randomized. We also present a static 2-approximation algorithm for t
he size kappa of the minimum vertex cut in a graph, which takes time O
(n(2) min(root n, kappa)). This is a factor of kappa faster than the b
est kappa n(2))min(root n, kappa)). We give an insertions-only algorit
hm for maintaining a (2 + epsilon)-approximation of the minimum vertex
cut with amortized insertion time O(n/epsilon). (C) 1997 Academic Pre
ss.