D.M. Silva, R.M.A. Silva, G.R. Mateus, J.F. Gonçalves, M.G.C. Resende, and P. Festa
Optimization Letters, vol. 8, pp. 1225-1243, 2014
ABSTRACT
This paper
presents a new edge-swap heuristic for generating spanning trees with a
minimum number of branch vertices, i.e. vertices of degree greater than
two. This problem was introduced in Gargano et al. (2002) and has
been called the minimum branch vertices (MBV) problem by Cerulli et al.
(2009). The heuristic starts with a random spanning tree and
iteratively reduces the number of branch vertices by swapping tree
edges with edges not currently in the tree. It can be easily
implemented as a multi-start heuristic. We report on extensive
computational experiments comparing single-start and multi-start
variants on our heuristic with other heuristics previously proposed in
the literature.