Parameterized Dynamic Data Structure for Split Completion

Prelegent(ci)

Konrad Majewski

Język referatu

angielski

Termin

18 października 2024 14:15

Pokój

p. 5060

Seminarium

Seminarium "Algorytmika"

---

We design a randomized data structure that, for a fully dynamic graph G updated by edge insertions and deletions and integers k, d fixed upon initialization, maintains the answer to the Split Completion problem: whether one can add k edges to G to obtain a split graph. The data structure can be initialized on an edgeless n-vertex graph in time n (kd log n)^{O(1)}, and the amortized time complexity of an update is 5^k (kd log n)^{O(1)}. The answer provided by the data structure is correct with probability 1-O(n^{-d}). 

This is a joint work with Michał Pilipczuk and Anna Zych-Pawlewicz.

---