Speaker
Aditi Dudeja
(University of Salzburg)
Description
In dynamic graph algorithms, the goal is to maintain a key property of the graph while an adversary makes changes to the graph in the form of edge deletions or insertions. The goal is to minimize the update time of the algorithm, which is the time taken by the algorithm to adapt to a single adversarial edge insertion or deletion and output accordingly. I will briefly talk about some algorithms that maintain a good approximation to the maximum matching in a dynamic unweighted graph. Then, I will describe a framework that extends these results to the more general case of weighted graphs. Moreover, this reduction is applicable to a number of different models such as distributed, massively parallel and streaming models.
