Please use this identifier to cite or link to this item:
|Title:||An edge-swap heuristic for generating spanning trees with minimum number of branch vertices|
José Fernando Gonçalves
|Abstract:||This paper presents a newedge-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. (Lect Notes Comput Sci 2380:355-365, 2002) and has been called the minimum branch vertices problem by Cerulli et al. (Comput Optim Appl 42:353-370, 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.|
|Appears in Collections:||LIAAD - Indexed Articles in Journals|
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.