# Maintaining a Large Matching and a Small Vertex Cover

Authors: Krzysztof Onak, Ronitt Rubinfeld
Conference: The 42nd ACM Symposium on Theory of Computing (STOC 2010).

Abstract: We consider the problem of maintaining a large matching and a small vertex cover in a dynamically changing graph. Each update to the graph is either an edge deletion or an edge insertion. We give the first randomized data structure that simultaneously achieves a constant approximation factor and handles a sequence of $K$ updates in $K\cdot \operatorname{polylog}(n)$ time, where $n$ is the number of vertices in the graph. Previous data structures require a polynomial amount of computation per update.

Conference version: [PDF] [PS]
BibTeX: [DBLP]