---
_id: '11875'
abstract:
- lang: eng
  text: 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].
article_processing_charge: No
arxiv: 1
author:
- first_name: Sayan
  full_name: Bhattacharya, Sayan
  last_name: Bhattacharya
- first_name: Monika H
  full_name: Henzinger, Monika H
  id: 540c9bbd-f2de-11ec-812d-d04a5be85630
  last_name: Henzinger
  orcid: 0000-0002-5008-6530
- first_name: Giuseppe F.
  full_name: Italiano, Giuseppe F.
  last_name: Italiano
citation:
  ama: 'Bhattacharya S, Henzinger MH, 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>'
  apa: 'Bhattacharya, S., Henzinger, M. H., &#38; Italiano, G. F. (2014). Deterministic
    fully dynamic data structures for vertex cover and matching. In <i>26th Annual
    ACM-SIAM Symposium on Discrete Algorithms</i> (pp. 785–804). San Diego, CA, United
    States: Society for Industrial and Applied Mathematics. <a href="https://doi.org/10.1137/1.9781611973730.54">https://doi.org/10.1137/1.9781611973730.54</a>'
  chicago: Bhattacharya, Sayan, Monika H Henzinger, and Giuseppe F. Italiano. “Deterministic
    Fully Dynamic Data Structures for Vertex Cover and Matching.” In <i>26th Annual
    ACM-SIAM Symposium on Discrete Algorithms</i>, 785–804. Society for Industrial
    and Applied Mathematics, 2014. <a href="https://doi.org/10.1137/1.9781611973730.54">https://doi.org/10.1137/1.9781611973730.54</a>.
  ieee: S. Bhattacharya, M. H. Henzinger, and G. F. Italiano, “Deterministic fully
    dynamic data structures for vertex cover and matching,” in <i>26th Annual ACM-SIAM
    Symposium on Discrete Algorithms</i>, San Diego, CA, United States, 2014, pp.
    785–804.
  ista: 'Bhattacharya S, Henzinger MH, Italiano GF. 2014. Deterministic fully dynamic
    data structures for vertex cover and matching. 26th Annual ACM-SIAM Symposium
    on Discrete Algorithms. SODA: Symposium on Discrete Algorithms, 785–804.'
  mla: Bhattacharya, Sayan, et al. “Deterministic Fully Dynamic Data Structures for
    Vertex Cover and Matching.” <i>26th Annual ACM-SIAM Symposium on Discrete Algorithms</i>,
    Society for Industrial and Applied Mathematics, 2014, pp. 785–804, doi:<a href="https://doi.org/10.1137/1.9781611973730.54">10.1137/1.9781611973730.54</a>.
  short: S. Bhattacharya, M.H. Henzinger, G.F. Italiano, in:, 26th Annual ACM-SIAM
    Symposium on Discrete Algorithms, Society for Industrial and Applied Mathematics,
    2014, pp. 785–804.
conference:
  end_date: 2015-01-06
  location: San Diego, CA, United States
  name: 'SODA: Symposium on Discrete Algorithms'
  start_date: 2015-01-04
date_created: 2022-08-16T12:36:42Z
date_published: 2014-01-01T00:00:00Z
date_updated: 2023-02-21T16:32:06Z
day: '01'
doi: 10.1137/1.9781611973730.54
extern: '1'
external_id:
  arxiv:
  - '1412.1318'
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://arxiv.org/abs/1412.1318
month: '01'
oa: 1
oa_version: Preprint
page: 785-804
publication: 26th Annual ACM-SIAM Symposium on Discrete Algorithms
publication_identifier:
  eisbn:
  - 978-1-61197-373-0
  isbn:
  - 978-1-61197-374-7
publication_status: published
publisher: Society for Industrial and Applied Mathematics
quality_controlled: '1'
related_material:
  record:
  - id: '11890'
    relation: later_version
    status: public
scopus_import: '1'
status: public
title: Deterministic fully dynamic data structures for vertex cover and matching
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2014'
...