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

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.
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/11386/1993201
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 22
  • ???jsp.display-item.citation.isi??? 20
social impact