We present the first deterministic data structures for maintaining approximate minimum vertex cover and maximum matching in a fully dynamic graph G = (V, E), with |V | = n and |E| = m, in o(m) 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+) approximation in O(min(n/, 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 [in 42nd ACM Symposium on Theory of Computing, Cambridge, MA, ACM, 2010, pp. 457–464].

Deterministic fully dynamic data structures for vertex cover and matching / Bhattacharya, Sayan; Henzinger, Monika; Italiano, Giuseppe Francesco. - In: SIAM JOURNAL ON COMPUTING. - ISSN 0097-5397. - 47:3(2018), pp. 859-887. [10.1137/140998925]

Deterministic fully dynamic data structures for vertex cover and matching

Italiano, Giuseppe F.
2018

Abstract

We present the first deterministic data structures for maintaining approximate minimum vertex cover and maximum matching in a fully dynamic graph G = (V, E), with |V | = n and |E| = m, in o(m) 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+) approximation in O(min(n/, 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 [in 42nd ACM Symposium on Theory of Computing, Cambridge, MA, ACM, 2010, pp. 457–464].
2018
Dynamic data structures; Fully dynamic algorithms; Maximum matching; Minimum vertex conver; Primal-dual method; Computer Science (all); Mathematics (all)
Deterministic fully dynamic data structures for vertex cover and matching / Bhattacharya, Sayan; Henzinger, Monika; Italiano, Giuseppe Francesco. - In: SIAM JOURNAL ON COMPUTING. - ISSN 0097-5397. - 47:3(2018), pp. 859-887. [10.1137/140998925]
File in questo prodotto:
File Dimensione Formato  
siam2018.pdf

Solo gestori archivio

Tipologia: Versione dell'editore
Licenza: DRM (Digital rights management) non definiti
Dimensione 471.66 kB
Formato Adobe PDF
471.66 kB Adobe PDF   Visualizza/Apri
Pubblicazioni consigliate

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11385/182812
Citazioni
  • Scopus 32
  • ???jsp.display-item.citation.isi??? 18
social impact