Geodesic
On calculation of the stability radius for a minimum spanning tree
Journal of the Belarusian State University. Mathematics and Informatics, Tome 1 (2017), pp. 34-38.

Voir la notice de l'article provenant de la source Math-Net.Ru

We consider a minimum spanning tree problem in the situation where weights of edges are exposed to independent perturbations. We study a quantitative characteristic of stability for a given optimal solutions of the problem. The characteristic is called the stability radius and defined as the limit level of edges weights perturbations which preserve optimality of a particular solution. We present an exact formula for the stability radius that allows calculating the radius in time which is extremely close to linear with respect to number of graph edges. This improves upon a well-known formula of an optimal solution for a linear combinatorial problem which requires complete enumeration of feasible solutions set whose cardinality may grow exponentially.
Keywords: minimum spanning tree problem; second-best spanning tree; sensitivity analysis of solutions; stability radius. 
@article{BGUMI_2017_1_a5,
     author = {Ya. Zhyvitsa and K. G. Kuz'min},
     title = {On calculation of the stability radius for a minimum spanning tree},
     journal = {Journal of the Belarusian State University. Mathematics and Informatics},
     pages = {34--38},
     publisher = {mathdoc},
     volume = {1},
     year = {2017},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/BGUMI_2017_1_a5/}
}
TY  - JOUR
AU  - Ya. Zhyvitsa
AU  - K. G. Kuz'min
TI  - On calculation of the stability radius for a minimum spanning tree
JO  - Journal of the Belarusian State University. Mathematics and Informatics
PY  - 2017
SP  - 34
EP  - 38
VL  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/BGUMI_2017_1_a5/
LA  - ru
ID  - BGUMI_2017_1_a5
ER  - 
%0 Journal Article
%A Ya. Zhyvitsa
%A K. G. Kuz'min
%T On calculation of the stability radius for a minimum spanning tree
%J Journal of the Belarusian State University. Mathematics and Informatics
%D 2017
%P 34-38
%V 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/BGUMI_2017_1_a5/
%G ru
%F BGUMI_2017_1_a5
Ya. Zhyvitsa; K. G. Kuz'min. On calculation of the stability radius for a minimum spanning tree. Journal of the Belarusian State University. Mathematics and Informatics, Tome 1 (2017), pp. 34-38. http://geodesic.mathdoc.fr/item/BGUMI_2017_1_a5/

[1] E. N. Gordeev, “Issledovanie ustoichivosti zadachi o kratchaishem ostovnom dereve v metrike l1”, Zhurnal vychisl. matematiki i matem. fiziki, 39(5) (1999), 770–778

[2] I. V. Sergienko, V. P. Shilo, “Zadachi diskretnoi optimizatsii. Problemy, metody resheniya, issledovaniya”, Kiev, 2003

[3] V. Emelichev, D. Podkopaev, “Quantitative stability analysis for vector problems of 0–1 programming”, Discret. Optim., 7(1/2) (2010), 48–63

[4] J. Roland, Y. Smet, J. R. Figueira, “On the calculation of stability radius for multi-objective combinatorial optimization problems by inverse optimization”, 4OR, 10(4) (2012), 379–389

[5] K. G. Kuzmin, “Edinyi podkhod k nakhozhdeniyu radiusov ustoichivosti v mnogokriterialnoi zadache o maksimalnom razreze grafa”, Diskret. analiz i issled. operatsii, 22(5) (2015), 30–51

[6] D. Eppstein, “Finding the k smallest spanning trees”, BIT Numer. Math., 32, # 2 (1992), 237–248

[7] G. N. Frederickson, “Ambivalent Data Structures for Dynamic 2-Edge-Connectivity and Smallest Spanning Trees Time”, SIAM J. Comput., 26(2) (1997), 484–538

[8] S. Pettie, “Sensitivity Analysis of Minimum Spanning Trees in Sub-Inverse-Ackermann Time”, J. Graph Algorithms Appl., 19(1) (2015), 375–391