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

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

New for: D1, D2, D3, D4, D5
<< Previous Entry Next Entry >> New Event Entry Edit this Entry Login to DB (to update, delete)
What and Who
Title:Fully dynamic maximal matching in O(log n) update time
Speaker:Manoj Gupta
coming from:Max-Planck-Institut für Informatik - D1
Speakers Bio:
Event Type:AG1 Mittagsseminar (own work)
Visibility:D1, D2, D3, D4, D5, SWS, RG1, MMCI
We use this to send out email in the morning.
Level:AG Audience
Date, Time and Location
Date:Tuesday, 10 July 2012
Duration:45 Minutes
Building:E1 4 - MPI-INF
We present an algorithm for maintaining maximal matching in a graph under addition and deletion of edges. Our data structure is randomized that takes O(log n) expected amortized time for each edge update where n is the number of vertices in the graph. While there is a trivial O(n) algorithm for edge update, the previous best known result for this problem for a graph with n vertices and m edges is O({(n+m)}^{0.7072})which is sub-linear only for a sparse graph. For the related problem of maximum matching, Onak and Rubinfield [STOC2010] designed a randomized data structure that achieves O(log^2 n) amortized time for each update for maintaining a c-approximate maximum matching for some large constant c. In contrast, we can maintain a factor two approximate maximum matching in O(log n) expected time per update as a direct corollary of the maximal matching scheme. This in turn also implies a two approximate vertex cover maintenance scheme that takes O(log n) expected time per update.
Name(s):Surender Baswana
Video Broadcast
Video Broadcast:NoTo Location:
Tags, Category, Keywords and additional notes
Attachments, File(s):
Created by:Timo Kötzing, 06/18/2012 03:32 PMLast modified by:Uwe Brahm/MPII/DE, 07/12/2012 12:26 PM
  • Uwe Brahm, 07/12/2012 12:26 PM
  • Timo Kötzing, 06/18/2012 03:32 PM -- Created document.