5
$\begingroup$

Given an undirected graph with at least one path connecting $u, v$, and a sequence of edges to be removed: $e_1, e_2, \dots$, I would like to quickly identify the point at which $u$ will be separated from $v$. Clearly this could be done by doing a full path search after each removed edge, but this is very expensive.

Is there a faster algorithm? (This is this question which asks about a related but more general and difficult situation, but it has gone unanswered.)

$\endgroup$

1 Answer 1

4
$\begingroup$

You can work your way backwards. Suppose the edges being removed are $e_1,\ldots,e_\ell$, and the rest of the edges form a set $E$. Start by determining the connected components induced by $E$, using a disjoint sets data structure. Now add the edges $e_\ell,\ldots,e_1$ in that order, updating the disjoint sets data structure, until $u$ and $v$ belong to the same connected component. The last edge encountered in this way is the one you seek.

$\endgroup$

Your Answer

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

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