my question is: Let $G$ be an undirected graph with weights. I want to find the set of the edges $e ∈ E(G)$, for which a minimum spanning tree $T_e$ with minimal weight exist, so $e$ is in $T_e$.
My Idea: Use Kruskal-Algorithm several times, so all possibilities of a MST with $e$ as an edge will appear. But I'm not sure how to find the set because it'll be depending on the graphs' structure. For instance if it only has two nodes and one edge the set would be one and so on.
Thanks for hints !
Let us denote this set of edges conatined in some MST by $M\subseteq E$ and let $w: \mathcal{P} E \to \mathbb{N}_0$ denote the weight function, i.e. for some set of edges $S\subseteq E$, $w(S)$ denotes the sum of the weights of the edges in $S$. I'm using the variables from http://en.wikipedia.org/wiki/Kruskal%27s_algorithm#Pseudocode.
You do not need to compute all possible MSTs wit h$e$ as an edge. You only need one MST and another (as small as possible) spanning tree containing $e$:
To check whether some $e\in E(G)$ is in $M$, you can do the following: compute just any MST $T$. Then start kruskal again: But as the initial set of edges in the tree don't use $A:=\emptyset$ but $A:=\{e\}$. Starting with that, compute a spanning tree $T_e$. Of course, it is $T_e$. Now we have: $$ e \in M \Leftrightarrow T_e\text{ is a MST} \Leftrightarrow w(T_e) = w(T). $$
If you want to check it for multiple candidates $e_1,\ldots,e_n$ you need to compute $T$ only once and you can abort computing $T_e$ if the weight of the tree you build already exceeds $w(T)$.
So computing the whole $M$ takes $\mathcal{O}(E^2 \cdot \log E)$. I'm not sure whether this is the optimal complexity for this problem.