Deterministic fully dynamic data structures for vertex cover and matching
Bhattacharya S, Henzinger MH, Italiano GF. 2018. Deterministic fully dynamic data structures for vertex cover and matching. SIAM Journal on Computing. 47(3), 859β887.
Download (ext.)
https://arxiv.org/abs/1412.1318
[Preprint]
Journal Article
| 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 πΊ=(π,πΈ), with |π|=π and |πΈ|=π, in π(πβΎβΎβ) time per update. In particular, for minimum vertex cover, we provide deterministic data structures for maintaining a (2+π) approximation in π(logπ/π2) amortized time per update. For maximum matching, we show how to maintain a (3+π) approximation in π(min(πβ/π,π1/3/π2) amortized time per update and a (4+π) approximation in π(π1/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].
Publishing Year
Date Published
2018-05-01
Journal Title
SIAM Journal on Computing
Publisher
Society for Industrial & Applied Mathematics
Volume
47
Issue
3
Page
859-887
ISSN
eISSN
IST-REx-ID
Cite this
Bhattacharya S, Henzinger MH, Italiano GF. Deterministic fully dynamic data structures for vertex cover and matching. SIAM Journal on Computing. 2018;47(3):859-887. doi:10.1137/140998925
Bhattacharya, S., Henzinger, M. H., & Italiano, G. F. (2018). Deterministic fully dynamic data structures for vertex cover and matching. SIAM Journal on Computing. Society for Industrial & Applied Mathematics. https://doi.org/10.1137/140998925
Bhattacharya, Sayan, Monika H Henzinger, and Giuseppe F. Italiano. βDeterministic Fully Dynamic Data Structures for Vertex Cover and Matching.β SIAM Journal on Computing. Society for Industrial & Applied Mathematics, 2018. https://doi.org/10.1137/140998925.
S. Bhattacharya, M. H. Henzinger, and G. F. Italiano, βDeterministic fully dynamic data structures for vertex cover and matching,β SIAM Journal on Computing, vol. 47, no. 3. Society for Industrial & Applied Mathematics, pp. 859β887, 2018.
Bhattacharya S, Henzinger MH, Italiano GF. 2018. Deterministic fully dynamic data structures for vertex cover and matching. SIAM Journal on Computing. 47(3), 859β887.
Bhattacharya, Sayan, et al. βDeterministic Fully Dynamic Data Structures for Vertex Cover and Matching.β SIAM Journal on Computing, vol. 47, no. 3, Society for Industrial & Applied Mathematics, 2018, pp. 859β87, doi:10.1137/140998925.
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:
Earlier Version
Export
Marked PublicationsOpen Data ISTA Research Explorer
Sources
arXiv 1412.1318