Deterministic fully dynamic data structures for vertex cover and matching Bhattacharya, Sayan Henzinger, Monika H ; https://orcid.org/0000-0002-5008-6530 Italiano, Giuseppe F. 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]. Society for Industrial and Applied Mathematics 2014 info:eu-repo/semantics/conferenceObject doc-type:conferenceObject text http://purl.org/coar/resource_type/c_5794 https://research-explorer.ista.ac.at/record/11875 Bhattacharya S, Henzinger M, Italiano GF. Deterministic fully dynamic data structures for vertex cover and matching. In: <i>26th Annual ACM-SIAM Symposium on Discrete Algorithms</i>. Society for Industrial and Applied Mathematics; 2014:785-804. doi:<a href="https://doi.org/10.1137/1.9781611973730.54">10.1137/1.9781611973730.54</a> eng info:eu-repo/semantics/altIdentifier/doi/10.1137/1.9781611973730.54 info:eu-repo/semantics/altIdentifier/isbn/978-1-61197-374-7 info:eu-repo/semantics/altIdentifier/e-isbn/978-1-61197-373-0 info:eu-repo/semantics/altIdentifier/arxiv/1412.1318 info:eu-repo/semantics/openAccess