let MST be the minimum spanning tree of a weighted finite graph; what can be said about the weight-optimality of the trees generated from the MST by sequentially exchanging a tree edge with a non-tree edge that incurs the least weight-increase and brings the tree topology closer to a desired target topology?
Applications are generating short Hamilton paths from MSTs or generating trees without vertices of degree 2 in order to be able to generate a Halin graph by threading the leaf nodes and then efficiently calculate the shortest Hamilton cycle in it.
The current method of choice is to manipulate tree-topology by means of adding vertex weights and recalculating the MST; it is however challenging to calculate a set of vertex weights that will render the resulting MST in the desired topology, whereas
exchanging edges seems attractive because it is more pragmatic, but how does the weight of the generated trees compare to that of MSTs after vertex weights have been added?
