Finding the k most vital edges with respect to minimum spanning tree
Hong Shen · 2002
For a connected, undirected and weighted graph G=(V, E), the problem of finding the k most vital edges of G with respect to minimum spanning tree is to find k edges in G whose removal will cause greatest weight increase in the minimum spanning tree of the remaining graph. This problem is known to be NP-hard for arbitrary k. In this paper, we first describe a simple exact algorithm for this problem, based on the approach of edge replacement in the minimum spanning tree of G. Next we present polynomial-time randomized algorithms that produce optimal and approximate solutions to this problem. For |V|=n and |E|=m, our algorithm producing optimal solution has a time complexity of O(mn) with probability of success at e/sup -/k/sup 2//2(m-n-1)-2 log/sub c/ k/k-4, c=1+1/2/sup k//2, and the algorithm producing approximate solution runs in time O(mn+nk/sup 2/ log k) and yields results within factor 2 to the optimal one. Finally we show that both of our randomized algorithms can be easily parallelized. On a CREW PRAM, the first algorithm runs in O(n) time using n/sup 2/ processors, and the second algorithm runs in O(log/sup 2/ n) time using mn/log n processors.