max planck institut
informatik

# MPI-INF or MPI-SWS or Local Campus Event Calendar

 << Previous Entry Next Entry >> New Event Entry Edit this Entry Login to DB (to update, delete)
Title: Deterministic Fully Dynamic Data Structures for Vertex Cover and Matching Sayan Bhattacharya Theoretical Computer Science Group, Institute of Mathematical Sciences Assistant Professor, Institute of Mathematical Sciences AG1 Mittagsseminar (own work) D1, D2, D3, D4, D5, RG1, SWS, MMCIWe use this to send out email in the morning. AG Audience English
Date: Tuesday, 30 June 2015 13:00 60 Minutes Saarbrücken E1 4 024
 We present the first deterministic data structures for maintaining approximate minimum vertex cover and maximum matching in a fully dynamic graph $G = (V,E)$, with $|V| = n$ and $|E| =m$, 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(\min(\sqrt{n}/\epsilon, 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 from STOC' 2010.
Name(s): Arjit Ghosh agosh@mpi-inf.mpg.de