The complexity of minimum ratio spanning tree problems

The complexity of minimum ratio spanning tree problems

0.00 Avg rating0 Votes
Article ID: iaor20051928
Country: Netherlands
Volume: 30
Issue: 4
Start Page Number: 335
End Page Number: 346
Publication Date: Dec 2004
Journal: Journal of Global Optimization
Authors: ,
Abstract:

We examine the complexity of two minimum spanning tree problems with rational objective functions. We show that the Minimum Ratio Spanning Tree problem is NP-hard when the denominator is unrestricted in sign, thereby sharpening a previous complexity result. We then consider an extension of this problem where the objective function is the sum of two linear ratios whose numerators and denominators are strictly positive. This problem is shown to be NP-hard as well. We conclude with some results characterizing sufficient conditions for a globally optimal solution.

Reviews

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