Premium
Reoptimization of the minimum spanning tree
Author(s) -
Paschos Stratos A.,
Paschos Vangelis Th.
Publication year - 2011
Publication title -
wiley interdisciplinary reviews: computational statistics
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.693
H-Index - 38
eISSN - 1939-0068
pISSN - 1939-5108
DOI - 10.1002/wics.204
Subject(s) - spanning tree , minimum spanning tree , computation , mathematical optimization , kruskal's algorithm , vertex (graph theory) , computer science , tree (set theory) , combinatorics , focus (optics) , dynamic programming , mathematics , algorithm , graph , physics , optics
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