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

• Tipo: Artigo em Revista Científica Internacional
• Data: 2014

Autores

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

Revista

Título: Optimization Letters

Vol. 8

Páginas: 1225-1243

ISSN: 1862-4472

Editora: Springer Nature

Indexação

ISI Web of Knowledge - 8 Citações

Scopus - 10 Citações

Classificação Científica

FOS: Ciências da engenharia e tecnologias > Biotecnologia industrial

Outras Informações

ID Authenticus: 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.

Idioma: Inglês

Tipo (Avaliação Docente): Científica

Nº de páginas: 19