[{"type":"conference","author":[{"first_name":"Sayan","full_name":"Bhattacharya, Sayan","last_name":"Bhattacharya"},{"last_name":"Henzinger","first_name":"Monika H","full_name":"Henzinger, Monika H","orcid":"0000-0002-5008-6530","id":"540c9bbd-f2de-11ec-812d-d04a5be85630"},{"full_name":"Italiano, Giuseppe F.","first_name":"Giuseppe F.","last_name":"Italiano"}],"day":"01","conference":{"name":"SODA: Symposium on Discrete Algorithms","start_date":"2015-01-04","end_date":"2015-01-06","location":"San Diego, CA, United States"},"title":"Deterministic fully dynamic data structures for vertex cover and matching","citation":{"short":"S. Bhattacharya, M.H. Henzinger, G.F. Italiano, in:, 26th Annual ACM-SIAM Symposium on Discrete Algorithms, Society for Industrial and Applied Mathematics, 2014, pp. 785–804.","apa":"Bhattacharya, S., Henzinger, M. H., &#38; Italiano, G. F. (2014). Deterministic fully dynamic data structures for vertex cover and matching. In <i>26th Annual ACM-SIAM Symposium on Discrete Algorithms</i> (pp. 785–804). San Diego, CA, United States: Society for Industrial and Applied Mathematics. <a href=\"https://doi.org/10.1137/1.9781611973730.54\">https://doi.org/10.1137/1.9781611973730.54</a>","ama":"Bhattacharya S, Henzinger MH, Italiano GF. Deterministic fully dynamic data structures for vertex cover and matching. In: <i>26th Annual ACM-SIAM Symposium on Discrete Algorithms</i>. Society for Industrial and Applied Mathematics; 2014:785-804. doi:<a href=\"https://doi.org/10.1137/1.9781611973730.54\">10.1137/1.9781611973730.54</a>","ista":"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.","ieee":"S. Bhattacharya, M. H. Henzinger, and G. F. Italiano, “Deterministic fully dynamic data structures for vertex cover and matching,” in <i>26th Annual ACM-SIAM Symposium on Discrete Algorithms</i>, San Diego, CA, United States, 2014, pp. 785–804.","chicago":"Bhattacharya, Sayan, Monika H Henzinger, and Giuseppe F. Italiano. “Deterministic Fully Dynamic Data Structures for Vertex Cover and Matching.” In <i>26th Annual ACM-SIAM Symposium on Discrete Algorithms</i>, 785–804. Society for Industrial and Applied Mathematics, 2014. <a href=\"https://doi.org/10.1137/1.9781611973730.54\">https://doi.org/10.1137/1.9781611973730.54</a>.","mla":"Bhattacharya, Sayan, et al. “Deterministic Fully Dynamic Data Structures for Vertex Cover and Matching.” <i>26th Annual ACM-SIAM Symposium on Discrete Algorithms</i>, Society for Industrial and Applied Mathematics, 2014, pp. 785–804, doi:<a href=\"https://doi.org/10.1137/1.9781611973730.54\">10.1137/1.9781611973730.54</a>."},"doi":"10.1137/1.9781611973730.54","language":[{"iso":"eng"}],"related_material":{"record":[{"relation":"later_version","id":"11890","status":"public"}]},"date_created":"2022-08-16T12:36:42Z","extern":"1","month":"01","page":"785-804","status":"public","quality_controlled":"1","publication":"26th Annual ACM-SIAM Symposium on Discrete Algorithms","publisher":"Society for Industrial and Applied Mathematics","year":"2014","oa_version":"Preprint","publication_identifier":{"eisbn":["978-1-61197-373-0"],"isbn":["978-1-61197-374-7"]},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","date_updated":"2023-02-21T16:32:06Z","scopus_import":"1","external_id":{"arxiv":["1412.1318"]},"date_published":"2014-01-01T00:00:00Z","_id":"11875","abstract":[{"text":"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].","lang":"eng"}],"article_processing_charge":"No","arxiv":1,"oa":1,"main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1412.1318"}],"publication_status":"published"}]