On 28.05.2015 as a part of our Foundation for Polish Science Algorithmic Miniworkshop series we will host Giuseppe F. Italiano from University of Rome “Tor Vergata”. He will give a talk on his recent result on “Deterministic Fully Dynamic Data Structures for Vertex Cover and Matching”. The abstract is given below.

We plan to have a group discussion and joint hamburger lunch after his talk.

Abstract:

We present the first deterministic data structures for maintaining

approximate minimum vertex cover and maximum matching in a fully

dynamic graph in $o(\sqrt{m}\,)$ time per update. In particular, for

minimum vertex cover we provide deterministic data structures for

maintaining a $(2+\eps)$ approximation in $O(\log n/\eps^2)$ amortized

time per update. For maximum matching, we show how to maintain a

$(3+\eps)$ approximation in $O(m^{1/3}/\eps^2)$ {\em amortized} time

per update, and a $(4+\eps)$ approximation in $O(m^{1/3}/\eps^2)$ {\em

worst-case} time per update. Our data structure for fully dynamic

minimum vertex cover is essentially near-optimal and settles an open

problem by Onak and Rubinfeld~\cite{OnakR10}.

Joint work with Sayan Bhattacharya and Monika Henzinger.