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

Research output: Journal Publications and ReviewsRGC 21 - Publication in refereed journalpeer-review

21 Scopus Citations
View graph of relations

Author(s)

Detail(s)

Original languageEnglish
Pages (from-to)319-327
Journal / PublicationDiscrete Applied Mathematics
Volume113
Issue number2-3
Publication statusPublished - 15 Oct 2001
Externally publishedYes

Abstract

Assume that G(V,E) is a weighted, undirected, connected graph with n vertices. The k most vital edge problem with respect to a minimum spanning tree is 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 tree in the resulting graph G(V,E-S*). In this paper, an improved algorithm for the problem with fixed k, k≥2, has been presented. The proposed algorithm runs in time O(nkα((k+1)(n-1),n)), which improves a previously known result by an O(n/α((k+1)(n-1),n)) factor, where α is a functional inverse of Ackermann's function which grows very slow. The parallel version of the algorithm takes O(lognloglogn) time using O(nk/logn) processors on a CREW PRAM. © 2001 Elsevier Science B.V.

Research Area(s)

  • Combinatorial algorithms, Minimum spanning trees, Most vital edges, Network optimization, Parallel algorithms

Bibliographic Note

Publication details (e.g. title, author(s), publication statuses and dates) are captured on an “AS IS” and “AS AVAILABLE” basis at the time of record harvesting from the data source. Suggestions for further amendments or supplementary information can be sent to [email protected].