0
$\begingroup$

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 !

$\endgroup$
  • $\begingroup$ So you want to find every single minimum spanning tree, and then take the set of all the edges in those MSTs? $\endgroup$ – Sultan of Swing Jan 2 '15 at 3:48
  • $\begingroup$ Yes, I want to find every single MST with e as an edge in it. $\endgroup$ – pinkpanther5 Jan 2 '15 at 11:25
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.