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


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.