A global optimization algorithm for solving the minimum multiple ratio spanning tree problem

A global optimization algorithm for solving the minimum multiple ratio spanning tree problem

0.00 Avg rating0 Votes
Article ID: iaor20134048
Volume: 56
Issue: 3
Start Page Number: 1029
End Page Number: 1043
Publication Date: Jul 2013
Journal: Journal of Global Optimization
Authors: , ,
Keywords: global optimization, minimum spanning trees
Abstract:

This paper studies the sum‐of‐ratios version of the classical minimum spanning tree problem. We describe a branch‐and‐bound algorithm for solving the general version of the problem based on its image space representation. The suggested approach specifically addresses the difficulties arising in the case when the number of ratios exceeds two. The efficacy of our approach is demonstrated on randomly generated complete and sparse graph instances.

Reviews

Required fields are marked *. Your email address will not be published.