Deterministic fully dynamic data structures for vertex cover and matching

Bhattacharya, Sayan; Henzinger, Monika H; Italiano, Giuseppe F.

Earlier Version

Deterministic fully dynamic data structures for vertex cover and matching

Bhattacharya S, Henzinger M, 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.

Download (ext.)

https://arxiv.org/abs/1412.1318 [Preprint]

DOI

10.1137/1.9781611973730.54

Conference Paper | Published | English

Scopus indexed

Author

Bhattacharya, Sayan; Henzinger, Monika^ISTA ; Italiano, Giuseppe F.

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].

Publishing Year

2014

Date Published

2014-01-01

Proceedings Title

26th Annual ACM-SIAM Symposium on Discrete Algorithms

Publisher

Society for Industrial and Applied Mathematics

Page

785-804

Conference

SODA: Symposium on Discrete Algorithms

Conference Location

San Diego, CA, United States

Conference Date

2015-01-04 – 2015-01-06

ISBN

978-1-61197-374-7

IST-REx-ID

11875

Cite this

Bhattacharya S, Henzinger M, Italiano GF. Deterministic fully dynamic data structures for vertex cover and matching. In: 26th Annual ACM-SIAM Symposium on Discrete Algorithms. Society for Industrial and Applied Mathematics; 2014:785-804. doi:10.1137/1.9781611973730.54

Bhattacharya, S., Henzinger, M., & Italiano, G. F. (2014). Deterministic fully dynamic data structures for vertex cover and matching. In 26th Annual ACM-SIAM Symposium on Discrete Algorithms (pp. 785–804). San Diego, CA, United States: Society for Industrial and Applied Mathematics. https://doi.org/10.1137/1.9781611973730.54

Bhattacharya, Sayan, Monika Henzinger, and Giuseppe F. Italiano. “Deterministic Fully Dynamic Data Structures for Vertex Cover and Matching.” In 26th Annual ACM-SIAM Symposium on Discrete Algorithms, 785–804. Society for Industrial and Applied Mathematics, 2014. https://doi.org/10.1137/1.9781611973730.54.

S. Bhattacharya, M. Henzinger, and G. F. Italiano, “Deterministic fully dynamic data structures for vertex cover and matching,” in 26th Annual ACM-SIAM Symposium on Discrete Algorithms, San Diego, CA, United States, 2014, pp. 785–804.

Bhattacharya, Sayan, et al. “Deterministic Fully Dynamic Data Structures for Vertex Cover and Matching.” 26th Annual ACM-SIAM Symposium on Discrete Algorithms, Society for Industrial and Applied Mathematics, 2014, pp. 785–804, doi:10.1137/1.9781611973730.54.

All files available under the following license(s):

Copyright Statement: