We consider the following problem. Given a graph G and a real valued weight for each edge in G, find a spanning tree T of G such that the difference in weight between the most and least weighted edge in T is minimized. We show an O(m log n) algorithm for this problem, where m is the number of edges and n is the number of vertices in G. This algorithm improves the algorithm given by Camerini et al.  for the same problem.
All Science Journal Classification (ASJC) codes
- Discrete Mathematics and Combinatorics
- Applied Mathematics