Let $G = (V,E)$ with a weight function $w(e)$ for $e \in E$.Let $T$ be the set of minimal spanning trees of $G$.I am interested in finding $\min_{t \in T} \max_{e \in t} w(e)$, where $t$ ranges over minimal spanning trees.This is the minimally heaviest edge in all minimal spanning trees.Is there an algorithm for finding this value? What if I am interested in finding this value approximately, without exploring the whole graph (because the graph is quite large)? Is there a sampling or an approximate algorithm in this case?
Is there an algorithm for finding the maximal edge weight over all spanning trees?
ds.algorithms;graph theory;graph algorithms;approximation algorithms