---
res:
  bibo_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].@eng
  bibo_authorlist:
  - foaf_Person:
      foaf_givenName: Sayan
      foaf_name: Bhattacharya, Sayan
      foaf_surname: Bhattacharya
  - foaf_Person:
      foaf_givenName: Monika H
      foaf_name: Henzinger, Monika H
      foaf_surname: Henzinger
      foaf_workInfoHomepage: http://www.librecat.org/personId=540c9bbd-f2de-11ec-812d-d04a5be85630
    orcid: 0000-0002-5008-6530
  - foaf_Person:
      foaf_givenName: Giuseppe F.
      foaf_name: Italiano, Giuseppe F.
      foaf_surname: Italiano
  bibo_doi: 10.1137/1.9781611973730.54
  dct_date: 2014^xs_gYear
  dct_isPartOf:
  - http://id.crossref.org/issn/978-1-61197-374-7
  dct_language: eng
  dct_publisher: Society for Industrial and Applied Mathematics@
  dct_title: Deterministic fully dynamic data structures for vertex cover and matching@
...