Question

Let G = (V,E) be a weighted undirected graph and let T be a Minimum Spanning Tree (MST) of G maintained using adjacency lists. Suppose a new weighted edge ( u, v) $\in$ V x V is added to G. The worst case time complexity of determining if T is still an MST of the resultant graph is

• A. $\Theta \left(|E||V|\right)$
• B. $\Theta \left(|E|log|V|\right)$
• C. $\Theta \left(|V|\right)$
• D. $\Theta (|E|+|V|)$

Answer 1

The correct option is C $\Theta \left(|V|\right)$

$\Theta \left(|V|\right)$