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

✍ Scribed by Monika Rauch Henzinger

• Publisher: Elsevier Science
• Year: 1997
• Tongue: English
• Weight: 329 KB
• Volume: 24
• Category: Article
• ISSN: 0196-6774
• DOI: 10.1006/jagm.1997.0855

✦ Synopsis

This paper presents insertions-only algorithms for maintaining the exact andror 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

for a 1 q ⑀ -approximation, and O log n for the exact size, where n is the number of nodes in the graph and is the size of the minimum Ž . cut. The 2 q ⑀ -approximation algorithm and the exact algorithm are determinis-Ž . tic; the 1 q ⑀ -approximation algorithm is randomized. We also present a static 2-approximation algorithm for the size of the minimum vertex cut in a graph, ' Ž Ž . . which takes time O n min n , . This is a factor of faster than the best ŽŽ 3 algorithm for computing the exact size, which takes time O n q 2 ' . Ž .. Ž . n min n , . We give an insertions-only algorithm for maintaining a 2 q ⑀ -Ž . approximation of the minimum vertex cut with amortized insertion time O nr⑀ .