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
Authors: Silva,RMA
José Fernando Gonçalves
Issue Date: 2014
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.
metadata.dc.type: article
Appears in Collections:LIAAD - Indexed Articles in Journals

Files in This Item:
File Description SizeFormat 
P-008-ND2.pdf248.59 kBAdobe PDFThumbnail

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.