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, and P. Festa

Experimental Algorithms, Proceedings of the 10th International Symposium (SEA 2011), Lecture Notes in Computer Sciencevol. 6630, pp. 421-433, 2011. 


This paper presents a new approach to solve the NP-complete minimum branch vertices problem (MBV) introduced by Gargano et al. [1]. In spite of being a recently proposed problem in the network op- timization literature, there are some heuristics to solve it [3]. The main contribution of this paper consists in a new heuristic based on the iter- ative refinement approach proposed by Deo and Kumar [2]. The experi- mental 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.

PDF file of full paper


Go back

Mauricio G.C. Resende's Home Page

Last modified: 17 May 2011

Copyright Notice