Name
Title | ||
|---|---|---|
An edge-swap heuristic for generating spanning trees with minimum number of branch vertices. |
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. |
Year | DOI | Venue |
|---|---|---|
2014 | 10.1007/s11590-013-0665-y | Optimization Letters |
Keywords | Field | DocType |
Constrained spanning trees, Branch vertices, Minimum branch vertices problem, Heuristic, Multi-start heuristic, Edge swapping | Swap (computer programming),Discrete mathematics,Mathematical optimization,Combinatorics,Heuristic,Minimum degree spanning tree,Vertex (geometry),Heuristics,Spanning tree,Swap (finance),Mathematics,Minimum spanning tree | Journal |
Volume | Issue | ISSN |
8 | 4 | 1862-4480 |
Citations | PageRank | References |
7 | 0.53 | 7 |
Authors | ||
6 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Ricardo M. A. Silva | 1 | 65 | 9.02 |
| Diego M. Silva | 2 | 12 | 0.99 |
| Mauricio G. C. Resende | 3 | 3729 | 336.98 |
| Geraldo R. Mateus | 4 | 134 | 13.00 |
| José Fernando Gonçalves | 5 | 736 | 37.31 |
| Paola Festa | 6 | 287 | 25.32 |