Efficient determination of the k most vital edges for the minimum spanning tree problem

详细信息	查看全文 | 推荐本文 |

• 作者：Cristina Bazgan^a ; ^b ; ^{bazgan@lamsade.dauphine.fr} ; Sonia Toubaline^a ; ^{toubaline@lamsade.dauphine.fr} ; Daniel Vanderpooten^a ; ^{vdp@lamsade.dauphine.fr}
• 关键词：Most vital edges ; Minimum spanning tree ; Exact algorithms ; Mixed integer program
• 刊名：Computers and Operations Research
• 出版年：2012
• 期刊代码：3_03050548
• 类别：dec
• 出版时间：November, 2012
• 卷：39
• 期：11
• 页码：2888-2898
• 文件大小：299 K

摘要

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 enumeration 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.