• français
    • English
  • English 
    • français
    • English
  • Login
JavaScript is disabled for your browser. Some features of this site may not work without it.
BIRD Home

Browse

This CollectionBy Issue DateAuthorsTitlesSubjectsJournals BIRDResearch centres & CollectionsBy Issue DateAuthorsTitlesSubjectsJournals

My Account

Login

Statistics

View Usage Statistics

Fast Reoptimization for the Minimum Spanning Tree Problem

Thumbnail
View/Open
cahierLamsade279.pdf (350.0Kb)
Date
2010
Dewey
Recherche opérationnelle
Sujet
Minimum spanning tree; Approximation algorithms; Reoptimization
Journal issue
Journal of Discrete Algorithms
Volume
8
Number
3
Publication date
2010
Article pages
296-310
Publisher
Elsevier
DOI
http://dx.doi.org/10.1016/j.jda.2009.07.002
URI
https://basepub.dauphine.fr/handle/123456789/3867
Collections
  • LAMSADE : Publications
Metadata
Show full item record
Author
Boria, Nicolas
Paschos, Vangelis
Type
Article accepté pour publication ou publié
Abstract (EN)
We study reoptimization versions of the minimum spanning tree problem. The reoptimization setting can generally be formulated as follows: given an instance of the problem for which we already know some optimal solution, and given some “small” perturbations on this instance, is it possible to compute a new (optimal or at least near-optimal) solution for the modified instance without ex nihilo computation? We focus on two kinds of modifications: node-insertions and node-deletions. When k new nodes are inserted together with their incident edges, we mainly propose a fast strategy with complexity O(kn) which provides a max{2,3−(2/(k−1))}-approximation ratio, in complete metric graphs and another one that is optimal with complexity O(nlogn). On the other hand, when k nodes are deleted, we devise a strategy which in O(n) achieves approximation ratio bounded above by 2left ceiling|Lmax|/2right ceiling in complete metric graphs, where Lmax is the longest deleted path and |Lmax| is the number of its edges. For any of the approximation strategies, we also provide lower bounds on their approximation ratios.

  • Accueil Bibliothèque
  • Site de l'Université Paris-Dauphine
  • Contact
SCD Paris Dauphine - Place du Maréchal de Lattre de Tassigny 75775 Paris Cedex 16

 Content on this site is licensed under a Creative Commons 2.0 France (CC BY-NC-ND 2.0) license.