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: (i) Finding a spanning tree of G with the minimum number of branch vertices and (ii) 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.
Bounded-degree spanning tree problems: models and new algorithms
CERULLI, Raffaele;GENTILI, Monica;
2009-01-01
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: (i) Finding a spanning tree of G with the minimum number of branch vertices and (ii) 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.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
