Minimal ratio spanning trees

Abstract

Abstract Given an undirected graph G: (N;E) with a node set N and an edge set E and numbers C e and D e , 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.