Dynamic Bridge-Finding in Õ(log2 n) Amortized Time
Jacob Holm, Eva Rotenberg, Mikkel Thorup · Society for Industrial and Applied Mathematics eBooks · 2018
We present a deterministic fully-dynamic data structure for maintaining information about the bridges in a graph. We support updates in Õ((log n)2) amortized time, and can find a bridge in the component of any given vertex, or a bridge separating any two given vertices, in