Reoptimization of the minimum spanning tree

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. WIREs Comput Stat 2012, 4:211–217. doi: 10.1002/wics.204 This article is categorized under: Algorithms and Computational Methods > Dynamic Programming