3
$\begingroup$

I was wondering if there is any efficient (possibly armortized poly-logarithmic) online algorithm which supports counting (identification) of bridges- and non-bridges online, i.e. during a sequence of edge insertions and deletions for fixed set of vertices?

I have been using the algorithm presented in Schmidt's "A Simple Test on 2-Vertex- and 2-Edge-Connectivity", c.f. ArXiv, which is not online but a linear-time algorithm.

On the other hand I have also played around with a fully-dynamic connectivity algorithm, presented here. The problem here is that albeit the algorithm allows connectivity queries in poly-logarithmic time, to be able to say something about whether an edge is a bridge I actually need to perform a deletion and see if the connectivity changed.

Because my goal is to determine the number of bridges (or non-bridges) online, I would need to perform a deletion process for all bridges... And that can destroy the poly-logarithmic time complexity.

Any ideas?

Many thanks

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.