On recursive computation of minimum spanning trees for special partial graphs
Guntram Scheithauer · Optimization · 1985
Let G = (E N) be an undirected graph and T be a minimum spanning tree. If one edge e of T is removed from G then a new minimum spanning tree Te can be obtained from T recursively. In this paper an algorithm is proposed to determine n— 1 =card (T) new minimum spanning trees Te , one for each edge e, of T. with a total expense of O (card (N)2) computational operations. In addition an application to the symmetric traveling salesman problem is given.