Minimal ratio spanning trees
R. Chandrasekaran · Networks · 1977
Abstract Given an undirected graph G: (N;E) with a node set N and an edge set E and numbers Ce and De, e ϵ E, we provide a polynominally bounded algorithm to solve the problem: Find a spanning tree T such that the ratio magnified image is minimized. An extension to finding bases in matroids that minimize such ratio functions is immediate. It is shown that an algorithm that is “greedy,” in the sense of Edmonds [2], will not work for this problem.