|
|||||
|
|
An edge-swap heuristic for generating spanning trees with minimum number of branch vertices |
|
| Authors: | Ricardo M A Silva Diego M Silva Mauricio G C Resende Geraldo R Mateus José F Gonçalves Paola Festa |
| Institution: | 1. Center of Informatics, Federal University of Pernambuco, Av. Jornalista Anibal Fernandes, s/n, Cidade Universitária, CEP 50.740-560, Recife, PE, Brazil 2. Department of Computer Science, Federal University of Lavras, CEP 37200-000, Lavras, MG, Brazil 3. Algorithms and Optimization Research Department, AT&T Labs Research, 180 Park Avenue, Room C241, Florham Park, NJ, 07932, USA 4. Department of Computer Science, Federal University of Minas Gerais, CEP 31270-010, Belo Horizonte, MG, Brazil 5. LIAAD, Faculdade de Economia do Porto, Universidade do Porto, Rua Dr. Roberto Frias, s/n, 4200-464, Porto, Portugal 6. Department of Mathematics and Applications “R. Caccioppoli”, University of Napoli FEDERICO II, Compl., MSA, Via Cintia, 80126, Naples, Italy |
| 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. (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. |
| Keywords: | |
| 本文献已被 SpringerLink 等数据库收录！ | |