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) ∈ V × V is added to G. The worst case time complexity of determining if T is still an MST of the resultant graph is

GATE CSE 2020 Q41: Checking whether an MST survives the addition of one edge

Algorithms
2 marks
MCQ
−2/3 if wrong

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 \times V$ is added to $G$ . The worst case time complexity of determining if $T$ is still an MST of the resultant graph is

Try it: multiple choice: exactly one correct option

Wrong answer costs 2/3 mark in GATE.

Show answer and explanation

Answer: D (official GATE 2020 final answer key)

Concept used: Cycle property: the new edge closes exactly one cycle with $T$ ; $T$ stays minimum unless the new edge is lighter than the heaviest edge on that cycle.

First step: Find the $u$ – $v$ path in $T$ by a traversal of the tree (it has $|V| - 1$ edges) and track its maximum edge weight.

Full step-by-step solution

Detailed working, common mistakes and linked mock tests will be available with a free GATEiit account. Log-in is coming soon.

Share this question

WhatsAppDownload image

Source: official GATE 2020 CS question paper and final answer key, organised by IIT Delhi. Question paper · Answer key

PracticePractise Algorithms questions →Full paperAll GATE CSE 2020 questions →

GATE CSE 2020 Q41: Checking whether an MST survives the addition of one edge

Question

Full step-by-step solution

More Algorithms PYQs