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 as 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).