Fast reoptimization for the minimum spanning tree problem

Archetti, 2003, Reoptimizing the traveling salesman problem, Networks, 42, 154, 10.1002/net.10091 Ausiello, 2006, Reoptimization of minimum and maximum traveling salesman's tours, vol. 4059, 196 Bartusch, 1988, Scheduling project networks with resource constraints and time windows, Ann. Oper. Res., 16, 201, 10.1007/BF02283745 Bartusch, 1989, Design aspects of an advanced model-oriented DSS for scheduling problems in civil engineering, Decision Support Systems, 5, 321, 10.1016/0167-9236(89)90013-4 Bilò, 2008, Reoptimization of Steiner trees, vol. 5124, 258 Bilò, 2008, Reoptimization of weighted graph and covering problems, vol. 5426, 201 Böckenhauer, 2007, On the approximability of TSP on local modifications of optimally solved instances, Algorithm. Oper. Res., 2, 83 Böckenhauer, 2008, On the hardness of reoptimization, vol. 4910, 50 Chazelle, 2000, A minimum spanning tree algorithm with inverse-Ackerman type complexity, J. ACM, 47, 1028, 10.1145/355541.355562 Cheriton, 1976, Finding minimum spanning trees, SIAM J. Comput., 5, 724, 10.1137/0205051 Cormen, 2001 Eppstein, 1997, Sparsification – a technique for speeding up dynamic graph algorithms, J. ACM, 44, 669, 10.1145/265910.265914 Escoffier Henzinger, 1997, Maintaining minimum spanning trees in dynamic graphs, 594 J. Holm, K. de Lichtenberg, M. Thorup, Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity, in: Proc. STOC'98, 1998, pp. 79–89 Kruskal, 1956, On the shortest spanning subtree of a graph and the traveling salesman problem, Proc. Amer. Math. Soc., 7, 48, 10.1090/S0002-9939-1956-0078686-7 Schäffter, 1997, Scheduling with forbidden sets, Discrete Appl. Math., 72, 155, 10.1016/S0166-218X(96)00042-X Sleator, 1983, A data structure for dynamic trees, J. Comput. System Sci., 26, 362, 10.1016/0022-0000(83)90006-5 Tarjan, 1975, Efficience of a good but not linear set-union algorithm, J. ACM, 22, 215, 10.1145/321879.321884 Yao, 1975, An O(|E|loglog|V|) algorithm for finding minimum spanning trees, Inform. Process. Lett., 4, 21, 10.1016/0020-0190(75)90056-3