Max-Planck-Institut für Informatik
max planck institut
informatik
mpii logo Minerva of the Max Planck Society
 

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)
What and Who
Title:Deterministic Fully Dynamic Data Structures for Vertex Cover and Matching
Speaker:Sayan Bhattacharya
coming from:Theoretical Computer Science Group, Institute of Mathematical Sciences
Speakers Bio:Assistant Professor, Institute of Mathematical Sciences
Event Type:AG1 Mittagsseminar (own work)
Visibility:D1, D2, D3, D4, D5, RG1, SWS, MMCI
We use this to send out email in the morning.
Level:AG Audience
Language:English
Date, Time and Location
Date:Tuesday, 30 June 2015
Time:13:00
Duration:60 Minutes
Location:Saarbr├╝cken
Building:E1 4
Room:024
Abstract
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.

Contact
Name(s):Arjit Ghosh
EMail:agosh@mpi-inf.mpg.de
Video Broadcast
Video Broadcast:NoTo Location:
Tags, Category, Keywords and additional notes
Note:Appeared in SODA 2015.

This is a joint work with Monika Henzinger (University of Vienna, Austria) and Guiseppe Italiano (University of Rome "Tor Vergata", Italy).

Manuscript: http://arxiv.org/abs/1412.1318
Attachments, File(s):

Created by:Arjit Ghosh, 06/11/2015 01:01 PMLast modified by:Uwe Brahm/MPII/DE, 11/24/2016 04:13 PM
  • Arjit Ghosh, 06/11/2015 11:34 PM
  • Arjit Ghosh, 06/11/2015 01:01 PM -- Created document.