Show simple item record

dc.contributor.authorBazgan, Cristina
dc.contributor.authorToubaline, Sónia
dc.contributor.authorVanderpooten, Daniel
dc.date.accessioned2012-04-24T12:29:05Z
dc.date.available2012-04-24T12:29:05Z
dc.date.issued2011
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/9035
dc.language.isoenen
dc.subjectmost vital edges
dc.subjectmixed integer program
dc.subjectminimum spanning tree
dc.subjectexact algorithms
dc.subject.ddc003en
dc.titleEfficient Algorithms for Finding the k Most Vital Edges for the Minimum Spanning Tree Problem
dc.typeCommunication / Conférence
dc.description.abstractenWe 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.
dc.identifier.citationpages126-140
dc.relation.ispartoftitleCombinatorial Optimization and Applications 5th International Conference, COCOA 2011
dc.relation.ispartofeditorZhu, Xuding
dc.relation.ispartofpublnameSpringer
dc.relation.ispartofpublcityBerlin Heidelberg
dc.relation.ispartofdate2011
dc.description.sponsorshipprivateouien
dc.subject.ddclabelRecherche opérationnelleen
dc.relation.ispartofisbn978-3-642-22615-1
dc.relation.confcountryCHINA
dc.description.ssrncandidatenon
dc.description.halcandidateoui
dc.description.readershiprecherche
dc.description.audienceInternational
dc.date.updated2017-01-05T15:28:46Z


Files in this item

FilesSizeFormatView

There are no files associated with this item.

This item appears in the following Collection(s)

Show simple item record