Noon lecture

list of noon lectures ( 2005 | 2006 | 2007 | 2008 | 2009 | 2010 | 2011 | 2012 | 2013 | 2014 | 2015 | 2016 | 2017 | future lectures)

On 27.05.2014 at 15:00 in S5, there is the following noon lecture:

Estimating Streaming Maximum Matching in Planar Graphs and Beyond

Morteza Monemizadeh

University of Maryland

Abstract

We consider the problem of estimating the size of a maximum matching when the edges are revealed in a streaming fashion. Consider a graph G = (V, E) with n vertices and m edges. The input stream is a permutation of edges S=(e1,...,em} chosen by an adversary. The goal is to output an estimation of the size of a maximum matching. The algorithm is only allowed to use a small amount of memory (much smaller than n). When the underlying graph is planar, we present a simple and elegant streaming algorithm that with high probability estimates the size of a maximum matching within a constant factor using O~(n^{2/3}) memory space. The same guarantee generalizes to the family of graphs that have a constant arboricity. Graphs with bounded arboricity include, among other families of graphs, the graphs that exclude a constant-size minor. To the best of our knowledge, this is the first result

list of noon lectures ( 2005 | 2006 | 2007 | 2008 | 2009 | 2010 | 2011 | 2012 | 2013 | 2014 | 2015 | 2016 | 2017 | future lectures)

Webmaster: kamweb.mff.cuni.cz         Modified: 19. 10. 2010