<p>Let $G = (V,E)$ with a weight function $w(e)$ for $e \in E$.</p>

<p>Let $T$ be the set of <em>minimal</em> spanning trees of $G$.</p>

<p>I am interested in finding $\min_{t \in T} \max_{e \in t} w(e)$, where $t$ ranges over <em>minimal</em> spanning trees.</p>

<p>This is the minimally heaviest edge in all minimal spanning trees.</p>

<p>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?</p>

CC BY-SA 3.0
2012-08-21T19:01:21.190Z
This could easily be an exercise in an algorithms class. So, before leaving an answer, I'm curious: why do you want to know?
David Eppstein
CC BY-SA 3.0
2012-08-21T19:08:34.833Z
If the graph is so large that you cannot even read the whole graph, you might be interested in property testing algorithms (with a sublinear number of queries).  I do not know anything about property testing for this particular problem (I do not even know if property testing for this problem makes sense or not), but in general, the efficiency of property testing often depends on how exactly a graph is given, such as adjacency matrix, adjacency list, and both of them.
Tsuyoshi Ito
CC BY-SA 3.0
2012-08-21T23:34:17.640Z
@DavidEppstein this is not an exercise in an algorithms class for me - I am actually interested in implementing such an algorithm for certain type of graph exploration problem. I think the main indication that this is not a class exercise is because I would be satisfied with an approximate algorithm, since the graph is quite large, and I don't want to fully explore it. :-) But if finding this algorithm is as easy as an exercise, I would be curious to hear the solution!
Spanner
CC BY-SA 3.0
2012-08-21T23:47:38.353Z
about approximate algorithms: upper bounds on the heaviest edge are much better than lower bounds. @TsuyoshiIto thanks, I will look into property testing.
Spanner
CC BY-SA 3.0
2012-08-22T00:46:09.270Z
@Spanner: I think David was more curious as to what application this might have rather than controlling that this was not a exercise! And you didn't really answer...
Jérémie
CC BY-SA 3.0
2012-08-22T06:28:30.313Z
@Spanner, it is a good practice to include a motivation section in the question, that would help people understand what you are exactly looking for. Please check the *how to write a better question* section of our [FAQ].
Kaveh
CC BY-SA 3.0
2012-08-23T23:13:27.800Z
So... Does anybody knows a reference for how to solve this problem in linear time, if one is interested in the kth longest edge of the MST? This is possible, but I would like a refence... Thanks... --S
Sariel Har-Peled
<ds.algorithms><graph-theory><graph-algorithms><approximation-algorithms>
Is there an algorithm for finding the maximal edge weight over all spanning trees?
Spanner
# Is there an algorithm for finding the maximal edge weight over all spanning trees?

(Asked by: username_0 on 2012-08-21)

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?

**Tags:** ds.algorithms, graph-theory, graph-algorithms, approximation-algorithms

> **Comments:**
> **username_1**: This could easily be an exercise in an algorithms class. So, before leaving an answer, I'm curious: why do you want to know?  
> **username_2**: If the graph is so large that you cannot even read the whole graph, you might be interested in property testing algorithms (with a sublinear number of queries).  I do not know anything about property testing for this particular problem (I do not even know if property testing for this problem makes sense or not), but in general, the efficiency of property testing often depends on how exactly a graph is given, such as adjacency matrix, adjacency list, and both of them.  
> **username_0**: @DavidEppstein this is not an exercise in an algorithms class for me - I am actually interested in implementing such an algorithm for certain type of graph exploration problem. I think the main indication that this is not a class exercise is because I would be satisfied with an approximate algorithm, since the graph is quite large, and I don't want to fully explore it. :-) But if finding this algorithm is as easy as an exercise, I would be curious to hear the solution!  
> **username_0**: about approximate algorithms: upper bounds on the heaviest edge are much better than lower bounds. @TsuyoshiIto thanks, I will look into property testing.  
> **username_3**: @username_0: I think David was more curious as to what application this might have rather than controlling that this was not a exercise! And you didn't really answer...  
> **username_4**: @username_0, it is a good practice to include a motivation section in the question, that would help people understand what you are exactly looking for. Please check the *how to write a better question* section of our [FAQ].  
> **username_5**: So... Does anybody knows a reference for how to solve this problem in linear time, if one is interested in the kth longest edge of the MST? This is possible, but I would like a refence... Thanks... --S  

---

## 0 answers

