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.