
Fast Reoptimization for the Minimum Spanning Tree Problem
Boria, Nicolas; Paschos, Vangelis (2010), Fast Reoptimization for the Minimum Spanning Tree Problem, Journal of Discrete Algorithms, 8, 3, p. 296-310. http://dx.doi.org/10.1016/j.jda.2009.07.002
View/ Open
Type
Article accepté pour publication ou publiéDate
2010Journal name
Journal of Discrete AlgorithmsVolume
8Number
3Publisher
Elsevier
Pages
296-310
Publication identifier
Metadata
Show full item recordAbstract (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.Subjects / Keywords
Minimum spanning tree; Approximation algorithms; ReoptimizationRelated items
Showing items related by title and author.
-
Boria, Nicolas; Murat, Cécile; Paschos, Vangelis (2011) Communication / Conférence
-
Boria, Nicolas; Murat, Cécile; Paschos, Vangelis (2012) Article accepté pour publication ou publié
-
Paschos, Stratos; Paschos, Vangelis (2012) Article accepté pour publication ou publié
-
Paschos, Vangelis; Escoffier, Bruno; Milanic, Martin (2009) Article accepté pour publication ou publié
-
Boria, Nicolas; Monnot, Jérôme; Paschos, Vangelis (2012) Communication / Conférence