Finding the k most vital edges with respect to minimum spanning trees for fixed k
Research output: Journal Publications and Reviews › RGC 21 - Publication in refereed journal › peer-review
Author(s)
Detail(s)
Original language | English |
---|---|
Pages (from-to) | 319-327 |
Journal / Publication | Discrete Applied Mathematics |
Volume | 113 |
Issue number | 2-3 |
Publication status | Published - 15 Oct 2001 |
Externally published | Yes |
Link(s)
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].
Citation Format(s)
Finding the k most vital edges with respect to minimum spanning trees for fixed k. / Liang, Weifa.
In: Discrete Applied Mathematics, Vol. 113, No. 2-3, 15.10.2001, p. 319-327.
In: Discrete Applied Mathematics, Vol. 113, No. 2-3, 15.10.2001, p. 319-327.
Research output: Journal Publications and Reviews › RGC 21 - Publication in refereed journal › peer-review