I am working on the following exercise:
Consider an undirected graph $G = (V,E)$. Let $T^* = (V,E_{T^*})$ be a $MST$ and let $e$ be an edge in $E_{T^*}$. We define the set of all values that can be assigned to $w_e$ such that $T^*$ remains a MST as $I_e$.
- Show that $I_e$ is an interval.
- Devise an efficient algorithm to calculate $I_e$ for a given edge $e$.
- Devise an efficient algorithm that determines all $I_e$ in one step. It should be more efficient than repeatedly using the algorithm from 2.
I did the following:
- Consider an edge $e$ in $E_{T^*}$. Delete it from $G$ and find the new lowest weighted edge connecting the resulting components, say $e'$. The upper bound for $I_e$ is $w(e')$. The lower bound would be $-\infty$.
- Use the algorithm sketched in 1.
- I do not know what to do here. Could you help me?