Finding the k most vital edges with respect to minimum spanning trees for fixed k

Assume that G(V,E) is a weighted, undirected, connected graph with n vertic es. The k most vital edge problem with respect to a minimum spanning tree i s to find a set S* of k edges from E such that the removal of the edges in S* results in the greatest increase in the weight of the minimum spanning t ree in the resulting graph G(V,E-S*). In this paper, an improved algorithm for the problem with fixed k, k greater than or equal to 2, has been presen ted. The proposed algorithm runs in time O(n(k)alpha((k + 1)(n - 1), n)), w hich improves a previously known result by an O(n/alpha ((k + 1)(n - 1), n) ) factor, where a is a functional inverse of Ackermann's function which gro ws very slow. The parallel version of the algorithm takes O(log n log log n ) time using O(n(k)/log n) processors on a CREW PRAM. (C) 2001 Elsevier Sci ence B.V. All rights reserved.