This paper presents a new approach to solve the NP-complete minimum branch vertices problem (MBV). In spite of being a recently proposed problem in the network optimization literature, there are some heuristics to solve it. The main contribution of this paper consists in a new heuristic based on the iterative refinement approach. The experimental results suggest that this approach is capable of finding solutions that are better than the best known in the literature. In this work, for instance, the proposed heuristic found better solutions for 78% of the instances tested. The heuristic looks very promising for the solution of problems related with constrained spanning trees.
An Iterative Refinement Algorithm for the Minimum Branch Vertices Problem / D. M., Silva; R. M. A., Silva; G. R., Mateus; J. F., Gonçalves; M. G. C., Resende; Festa, Paola. - 6630:(2011), pp. 421-433. [10.1007/978-3-642-20662-7_36]
An Iterative Refinement Algorithm for the Minimum Branch Vertices Problem
FESTA, PAOLA
2011
Abstract
This paper presents a new approach to solve the NP-complete minimum branch vertices problem (MBV). In spite of being a recently proposed problem in the network optimization literature, there are some heuristics to solve it. The main contribution of this paper consists in a new heuristic based on the iterative refinement approach. The experimental results suggest that this approach is capable of finding solutions that are better than the best known in the literature. In this work, for instance, the proposed heuristic found better solutions for 78% of the instances tested. The heuristic looks very promising for the solution of problems related with constrained spanning trees.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
