Abstract
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. [1] for the same problem.
Original language | English (US) |
---|---|
Pages (from-to) | 173-175 |
Number of pages | 3 |
Journal | Discrete Applied Mathematics |
Volume | 20 |
Issue number | 2 |
DOIs | |
State | Published - Jun 1988 |
Externally published | Yes |
All Science Journal Classification (ASJC) codes
- Discrete Mathematics and Combinatorics
- Applied Mathematics