An edge-swap heuristic for generating spanning trees with minimum number of branch vertices

• Type: Article in International Scientific Journal
• Date: 2014

Authors

Ricardo M A Silva (Author) Other; Diego M Silva (Author) Other; Mauricio G C Resende (Author) Other; Geraldo R Mateus (Author) Other; Jose F Goncalves (Author) FEP; Paola Festa (Author) Other

Journal

Title: Optimization Letters

Vol. 8

Pages: 1225-1243

ISSN: 1862-4472

Publisher: Springer Nature

Indexing

ISI Web of Knowledge - 8 Citations

Scopus - 10 Citations

Scientific classification

FOS: Engineering and technology > Industrial biotechnology

Other information

Authenticus ID: P-008-ND2

DOI: 10.1007/s11590-013-0665-y

Abstract (EN): 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.

Language: English

Type (Professor's evaluation): Scientific

No. of pages: 19