Earlier Version
Deterministic fully dynamic data structures for vertex cover and matching
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.
Download (ext.)
https://arxiv.org/abs/1412.1318
[Preprint]
Conference Paper
| Published
| English
Scopus indexed
Author
Bhattacharya, Sayan;
Henzinger, MonikaISTA ;
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
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
IST-REx-ID
Cite this
Bhattacharya S, Henzinger MH, 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. H., & 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 H 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. H. 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 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.
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:
This Item is protected by copyright and/or related rights. [...]
Link(s) to Main File(s)
Access Level
Open Access
Material in ISTA:
Later Version
Export
Marked PublicationsOpen Data ISTA Research Explorer
Sources
arXiv 1412.1318