One of the basic motivations behind the Minimum Spanning Tree
Problem is the goal of designing a spanning network for a set of
nodes with minimum total cost. Here we explore another type of
objective: designing a spanning network for which the most
expensive edge is as cheap as possible.
Specifically, let G = (V, E) be a connected graph with n
vertices, m edges, and positive edges costs that are all distinct.
Let T = (V, E0 ) be...