in Algorithms
67 views
1 vote
1 vote

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

  1. $\Theta (\mid E \mid + \mid V \mid) \\$
  2. $\Theta (\mid E \mid \mid V \mid) \\$
  3. $\Theta(E \mid \log \mid V \mid) \\$
  4. $\Theta( \mid V \mid)$
in Algorithms
by
589 points
67 views

1 Answer

0 votes
0 votes
by
173 points
Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
Welcome to GATE CSE Doubts, where you can ask questions and receive answers from other members of the community.