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 F.. - 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].
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 F.. - 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 non definito
Dimensione 471.66 kB
Formato Adobe PDF
471.66 kB Adobe PDF   Visualizza/Apri
Pubblicazioni consigliate

Caricamento 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: http://hdl.handle.net/11385/182812
Citazioni
  • Scopus 22
  • ???jsp.display-item.citation.isi??? 14
social impact