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

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. 2011 Springer Science+Business Media, LLC.

authors

• Butenko, Sergiy

published proceedings

• JOURNAL OF GLOBAL OPTIMIZATION

author list (cited authors)

• Ursulenko, O., Butenko, S., & Prokopyev, O. A.

citation count

• 9

complete list of authors

• Ursulenko, Oleksii||Butenko, Sergiy||Prokopyev, Oleg A

publication date

• July 2013

publisher

• Springer Nature  Publisher

published in

• Journal of Global Optimization  Journal

keywords

• Fractional Programming
• Multiple-ratio Minimum Spanning Tree
• Sum-of-ratios

Digital Object Identifier (DOI)

• 10.1007/s10898-011-9832-9

start page

• 1029

end page

• 1043

volume

• 56

issue

• 3

URL

• http://dx.doi.org/10.1007/s10898-011-9832-9