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
Online bridge and nonbridge counting (identification)
ds.algorithms;graph theory;dynamic algorithms