Name
Title | ||
|---|---|---|
Efficient algorithms for finding the k most vital edges for the minimum spanning tree problem |
Abstract | ||
|---|---|---|
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.
|
Year | DOI | Venue |
|---|---|---|
2011 | 10.1007/978-3-642-22616-8_11 | COCOA |
Keywords | DocType | Volume |
vital edge,explicit enumeration algorithm,mixed integer program,tree problem,mixed integer programming formulation,k edge,implicit enumeration algorithm,general k,implicit exploration algorithm,previous algorithm,efficient algorithm,current best algorithm,fixed k | Conference | 6831 |
ISSN | Citations | PageRank |
0302-9743 | 1 | 0.37 |
References | Authors | |
14 | 3 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Cristina Bazgan | 1 | 679 | 62.76 |
| Sonia Toubaline | 2 | 60 | 7.54 |
| Daniel Vanderpooten | 3 | 1153 | 74.66 |