@inproceedings{11875,
  abstract     = {We present the first deterministic data structures for maintaining approximate minimum vertex cover and maximum matching in a fully dynamic graph in  time per update. In particular, for minimum vertex cover we provide deterministic data structures for maintaining a (2 + ε) approximation in O(log n/ε2) amortized time per update. For maximum matching, we show how to maintain a (3 + e) approximation in O(m1/3/ε2) amortized time per update, and a (4 + ε) approximation in O(m1/3/ε2) 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 [13].},
  author       = {Bhattacharya, Sayan and Henzinger, Monika H and Italiano, Giuseppe F.},
  booktitle    = {26th Annual ACM-SIAM Symposium on Discrete Algorithms},
  isbn         = {978-1-61197-374-7},
  location     = {San Diego, CA, United States},
  pages        = {785--804},
  publisher    = {Society for Industrial and Applied Mathematics},
  title        = {{Deterministic fully dynamic data structures for vertex cover and matching}},
  doi          = {10.1137/1.9781611973730.54},
  year         = {2014},
}