Fully dynamic biconnectivity in Õ(log² n) time

Prelegent(ci)

Marek Sokołowski

Afiliacja

Max Planck Institute for Informatics

Język referatu

angielski

Termin

28 lutego 2025 14:15

Pokój

p. 5060

Seminarium

Seminarium "Algorytmika"

---

We present a deterministic fully-dynamic data structure for maintaining information about the cut-vertices in a graph, i.e., the vertices whose removal would disconnect the graph. Our data structure supports insertion and deletion of edges, as well as queries to whether a pair of connected vertices are either biconnected, or can be separated by a cut-vertex, and in the latter case we support access to separating cut-vertices. All update operations are supported in amortized O(log² n (log log n)²) time in the Word RAM model, and queries take worst-case O(log n (log log n)²) time. Note that these time bounds match the current best for dynamic connectivity up to log log n factors. The previous best algorithm for biconnectivity had an update time of O(log⁴ n log log n) by Thorup [STOC’00], based on the O(log⁵ n) algorithm by Holm, de Lichtenberg, and Thorup [STOC’98].

During this talk, we will sketch how to obtain the improved running time via a series of reductions from the original problem into progressively simpler data structure problems. We will feature the top trees data structure maintaining fully dynamic forests and – time permitting – various biased tree data structures.

Joint work with Jacob Holm, Wojciech Nadara, and Eva Rotenberg.

---