Parameterized Dynamic Data Structure for Split Completion

Speaker(s)

Konrad Majewski

Language of the talk

English

Date

Oct. 18, 2024, 2:15 p.m.

Room

room 5060

Seminar

Seminar Algorithms

---

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.

---