Maintaining a large matching and a small vertex cover

Krzysztof Onak, Ronitt Rubinfeld

2010 · 102 citations · 14 references

DOIFull text

Open access

Concepts

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*polylog(n) time, where n is the number of vertices in the graph. Previous data structures require a polynomial amount of computation per update.

References

14