Reoptimization of the minimum spanning tree
Paschos, Stratos; Paschos, Vangelis (2012), Reoptimization of the minimum spanning tree, Wiley Interdisciplinary Reviews: Computational Statistics, 4, 2, p. 211-217. 10.1002/wics.204
TypeArticle accepté pour publication ou publié
Journal nameWiley Interdisciplinary Reviews: Computational Statistics
MetadataShow full item record
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Abstract (EN)We implement a fast reoptimization algorithm for MIN SPANNING TREE under vertex insertions, initially proposed and analyzed in the work of Boria and Paschos [Boria N, Paschos VTh. Fast reoptimization for the minimum spanning tree problem. J Discrete Algor 2010, 8:296–310] and study its experimental approximation behavior in randomly generated graphs. The reoptimization setting can briefly 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 computation from scratch? We focus in this article on the most popular modification: vertex-insertion.
Subjects / Keywordsapproximation; reoptimization; minimum spanning tree
Showing items related by title and author.