Name
Abstract | ||
|---|---|---|
Given a connected graph G, a vertex v of G is said to be a branch vertex if its degree is greater than 2. We consider two problems arising in the context of optical networks: Finding a spanning tree of G with the minimum number of branch vertices and Finding a spanning tree of G such that the degree sum of the branch vertices is minimized. For these NP-hard problems, heuristics, that give good quality solutions, do not exist in the literature. In this paper we analyze the relation between the problems, provide a single commodity flow formulation to solve the problems by means of a solver and develop different heuristic strategies to compute feasible solutions that are compared with the exact ones. Our extensive computational results show the algorithms to be very fast and effective. |
Year | DOI | Venue |
|---|---|---|
2009 | 10.1007/s10589-007-9120-2 | Comp. Opt. and Appl. |
Keywords | DocType | Volume |
Spanning trees,Spanning spiders,Branch vertices,Heuristics,Optical networks | Journal | 42 |
Issue | ISSN | Citations |
3 | 0926-6003 | 15 |
PageRank | References | Authors |
0.91 | 3 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| R. Cerulli | 1 | 252 | 23.85 |
| M. Gentili | 2 | 32 | 3.35 |
| A. Iossa | 3 | 18 | 1.65 |