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.