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.