On minimal cost-reliability ratio spanning trees and related problems

The minimal cost-reliability ratio spanning tree problem is to find a spanning tree such that the cost-reliability ratio is minimized. This problem can also be treated a a specific version of a more generalized problem discussed by Hassin and Tamir. By Hassin and Tamir’s approach, the minimal cost-reliability ratio spanning tree problem can be solved in O(q⁴) where q is the number of edges in the graph. In this paper, we reduce the complexity of the algorithm proposed by Hassin and Tamir to O(q³). Furthermore, using our approach, related algorithms proposed by Hassin and Tamir can also be improved by a factor of O(q).