Please use this identifier to cite or link to this item: http://repositorio.inesctec.pt/handle/123456789/5403
Title: An edge-swap heuristic for generating spanning trees with minimum number of branch vertices
Authors: Silva,RMA
Silva,DM
Resende,MGC
Mateus,GR
José Fernando Gonçalves
Festa,P
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.
URI: http://repositorio.inesctec.pt/handle/123456789/5403
http://dx.doi.org/10.1007/s11590-013-0665-y
metadata.dc.type: article
Publication
Appears in Collections:LIAAD - Indexed Articles in Journals

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


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