| Efficient Algorithms for Computing All Low s-t Edge Connectivities and Related (2007) | |||||||||||||||
Abstract | |||||||||||||||
| Given an undirected unweighted graph G =(V,E) andan integer k ≥ 1, we consider the problem of computing the edge connectivities of all those (s, t) vertex pairs, whose edge connectivity is at most k. We present an algorithm with expected running time Õ(m + nk3) for this problem, where |V | = n and |E | = m. Our output is a weighted tree T whose nodes are the sets V1,V2,...,Vℓ of a partition of V, with the property that the edge connectivity in G between any two vertices s ∈ Vi and t ∈ Vj, fori� = j, is equal to the weight of the lightest edge on the path between Vi and Vj in T. Also, two vertices s and t belong to the same Vi for any i if and only if they have an edge connectivity greater than k. Currently, the best algorithm for this problem needs to compute all-pairs min-cuts in an O(nk) edge graph; this | |||||||||||||||
Publication details | |||||||||||||||
| |||||||||||||||