Home
This Title All WIREs
WIREs RSS Feed
How to cite this WIREs title:
WIREs Comp Stat

Reoptimization of the minimum spanning tree

Full article on Wiley Online Library:   HTML PDF

Can't access this content? Tell your librarian.

Abstract 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

Plots of results on nonmetric graphs per values of |V| and |X|. (a) |V| = 500; (b) |V| = 1000; (c) |V| = 1500; (d) |V| = 2000; (e) |V| = 2500.

[ Normal View | Magnified View ]

Plots of results on metric graphs per values of |V| and |X|. (a) |V| = 500; (b) |V| = 1000; (c) |V| = 1500; (d) |V| = 2000; (e) |V| = 2500.

[ Normal View | Magnified View ]

Browse by Topic

Algorithms and Computational Methods > Dynamic Programming

Access to this WIREs title is by subscription only.

Recommend to Your
Librarian Now!

The latest WIREs articles in your inbox

Sign Up for Article Alerts