Efficient Algorithms for Finding the k Most Vital Edges for the Minimum Spanning Tree Problem
Bazgan, Cristina; Toubaline, Sónia; Vanderpooten, Daniel (2011), Efficient Algorithms for Finding the k Most Vital Edges for the Minimum Spanning Tree Problem, in Zhu, Xuding, Combinatorial Optimization and Applications 5th International Conference, COCOA 2011, Springer : Berlin Heidelberg, p. 126-140
TypeCommunication / Conférence
Book titleCombinatorial Optimization and Applications 5th International Conference, COCOA 2011
Book authorZhu, Xuding
MetadataShow full item record
Abstract (EN)We study in this paper the problem of finding in a graph a subset of k edges whose deletion causes the largest increase in the weight of a minimum spanning tree. We propose for this problem an explicit enumeration algorithm whose complexity, when compared to the current best algorithm, is better for general k but very slightly worse for fixed k. More interestingly, unlike in the previous algorithms, we can easily adapt our algorithm so as to transform it into an implicit exploration algorithm based on a branch and bound scheme. We also propose a mixed integer programming formulation for this problem. Computational results show a clear superiority of the implicit enumeration algorithm both over the explicit enumeration algorithm and the mixed integer program.
Subjects / Keywordsmost vital edges; mixed integer program; minimum spanning tree; exact algorithms
Showing items related by title and author.
Bazgan, Cristina; Toubaline, Sónia; Vanderpooten, Daniel (2013) Article accepté pour publication ou publié