Skip navigation
Skip navigation

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

Liang, Weifa


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...[Show more]

CollectionsANU Research Publications
Date published: 2001
Type: Journal article
Source: Discrete Applied Mathematics
DOI: 10.1016/S0166-218X(01)00189-5


File Description SizeFormat Image
01_Liang_Finding_the_k_most_vital_edges_2001.pdf147.67 kBAdobe PDF    Request a copy

Items in Open Research are protected by copyright, with all rights reserved, unless otherwise indicated.

Updated:  19 May 2020/ Responsible Officer:  University Librarian/ Page Contact:  Library Systems & Web Coordinator