• xmlui.mirage2.page-structure.header.title
    • français
    • English
  • Help
  • Login
  • Language 
    • Français
    • English
View Item 
  •   BIRD Home
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Publications
  • View Item
  •   BIRD Home
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Publications
  • View Item
JavaScript is disabled for your browser. Some features of this site may not work without it.

Browse

BIRDResearch centres & CollectionsBy Issue DateAuthorsTitlesTypeThis CollectionBy Issue DateAuthorsTitlesType

My Account

LoginRegister

Statistics

Most Popular ItemsStatistics by CountryMost Popular Authors
Thumbnail

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

Bazgan, Cristina; Toubaline, Sónia; Vanderpooten, Daniel (2012), Efficient determination of the k most vital edges for the minimum spanning tree problem, Computers and Operations Research, 39, 11, p. 2888-2898. 10.1016/j.cor.2012.02.023

View/Open
cocoa11.pdf (227.3Kb)
Type
Article accepté pour publication ou publié
Date
2012
Journal name
Computers and Operations Research
Volume
39
Number
11
Publisher
Elsevier
Pages
2888-2898
Publication identifier
10.1016/j.cor.2012.02.023
Metadata
Show full item record
Author(s)
Bazgan, Cristina
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Toubaline, Sónia
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Vanderpooten, Daniel
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
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 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.
Subjects / Keywords
Minimum spanning tree; Exact algorithms; Mixed integer program; Most vital edges

Related items

Showing items related by title and author.

  • Thumbnail
    Efficient Algorithms for Finding the k Most Vital Edges for the Minimum Spanning Tree Problem 
    Bazgan, Cristina; Toubaline, Sónia; Vanderpooten, Daniel (2011) Communication / Conférence
  • Thumbnail
    Critical edges/nodes for the minimum spanning tree problem: complexity and approximation 
    Bazgan, Cristina; Toubaline, Sónia; Vanderpooten, Daniel (2013) Article accepté pour publication ou publié
  • Thumbnail
    Complexity of determining the most vital elements for the 1-median and 1-center location problems 
    Bazgan, Cristina; Toubaline, Sónia; Vanderpooten, Daniel (2010) Communication / Conférence
  • Thumbnail
    Complexity of determining the most vital elements for the p-median and p-center location problems 
    Bazgan, Cristina; Toubaline, Sónia; Vanderpooten, Daniel (2013) Article accepté pour publication ou publié
  • Thumbnail
    Complexity of Most Vital Nodes for Independent Set in Graphs Related to Tree Structures 
    Bazgan, Cristina; Toubaline, Sónia; Tuza, Zsolt (2011) Communication / Conférence
Dauphine PSL Bibliothèque logo
Place du Maréchal de Lattre de Tassigny 75775 Paris Cedex 16
Phone: 01 44 05 40 94
Contact
Dauphine PSL logoEQUIS logoCreative Commons logo