1
$\begingroup$

We're given $T$ a minimal spanning tree (MST) of a non-directed, connected graph $G=(V,E)$ with non-negative weights for each edge $e \in E$. Let $e^* \in T$ be an edge in $T$ and let $G'=(V,E')$ be the graph which we get after removing $e^*$ ($E'=E\setminus \{e^*\}$). $G'$ is also connected.

I need to propose an algorithm which will run in $O(|E|)$ time and will restore $T$ such that it will yield an MST $T'$ for $G'$.

I'm really not sure if I'm in the right direction but this is what I thought of:

Let $e^*=(u,v)$.

a) We mark $e^*$ and remove it from $T$ and b) find the connected component of node $v$ by using BFS algorithm on $T$.

Now we have 2 connected components:

  1. the first starts from $v$ let's call it $S = T\setminus e^*$
  2. the second is $V\setminus S$

Clearly $e^*\notin S$ and $e^* \notin V\setminus S$. Also $S\neq V$ because otherwise we'd get a connected graph after the removal of $e^*$ of $n-1$ edges which would mean that there were $n$ edges in $T$ which is a contradiction since $T$ is a tree.

c) Then we start looking for a minimal edge $e'$ from $u\in V\setminus S$ to $v\in S$.

d) Once we found $e'$ we'll add it to $T$ and we'll get $T'$.

I'm having trouble with running times.

a) we need to traverse $G$ in order to find $e^*$ so it's the running time of BFS which is $O(|E|+|V|)$ and because $G$ is connected ($|E| \ge |V|-1$) then the time is $O(|E|)$.

b) BFS again so $O(|E|)$.

c) This could also be $O(|E|)$ because in the worst case the graph could be something like this: G

d) is O(1).

Improve this question
$\endgroup$
10
  • $\begingroup$ if $G'$ is also connected, won't $S = V$? Am I missing something here. $\endgroup$
    – LastIronStar
    Nov 20, 2017 at 10:19
  • 2
    $\begingroup$ Your running times are good: a) and b) For the BFS, you can even use T instead of G to do the BFS, so this step is O(|V|). c)This is O(|V|+|E|) because you'll just iterate through all vertices in S, and for each of them, for each edge going out of it, compare it to the current minimum iff the other end of the edge is in V\S. As you say, O(|V|+|E|) is O(|E|) here. d) is O(1). So your algorithm is indeed in O(|E|), does that answer your question ? $\endgroup$
    – gdelab
    Nov 22, 2017 at 16:35
  • 1
    $\begingroup$ In a tree BFS and preorder traversal are the same thing, so that's what it will do in practice ! $\endgroup$
    – gdelab
    Nov 22, 2017 at 16:45
  • 1
    $\begingroup$ (sorry i meant DFS above; but it does not change anything to the complexity, and a BFS would do the same). About c): O(|V|) come from the fact that S could have almost the size of V, and O(|E|) comes from the fact that you'll have to see at least once (at most twice) all edges with at least one vertex in S, and there could be up to |E|-1 of these. $\endgroup$
    – gdelab
    Nov 23, 2017 at 8:49
  • 1
    $\begingroup$ No. If you want the resulting tree to be minimal, you need to consider all edges that can connect S to V \ S, even if they do not touch e. One way of doing that is to iterate over nodes in S, and for each of them iterate over the edges going out of it, see if it goes to V\S, and if yes compare it to the previous minimal such edge. Depending on your data structure, maybe you can iterate directly over all edges, and consider only thos linking S to V \ S. $\endgroup$
    – gdelab
    Nov 23, 2017 at 9:28

1 Answer 1

Reset to default
1
$\begingroup$

This is just to confirm that OP has, in the course of updating his question, arrived at a well-written correct "algorithm which will run in $O(|E|)$ time and will restore $T$ such that it will yield an MST $T'$ for $G'$".

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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