conference paper published yes Sayan Bhattacharya author Monika H Henzinger author 540c9bbd-f2de-11ec-812d-d04a5be856300000-0002-5008-6530 Giuseppe F. Italiano author SODA: Symposium on Discrete Algorithms 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]. Society for Industrial and Applied Mathematics2014San Diego, CA, United States eng 978-1-61197-374-7 1412.131810.1137/1.9781611973730.54 785-804 https://research-explorer.ista.ac.at/record/11890 yes S. Bhattacharya, M. 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. Bhattacharya, S., Henzinger, M., &#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> 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>. Bhattacharya S, Henzinger M, 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> Bhattacharya, Sayan, Monika 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>. 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. S. Bhattacharya, M. Henzinger, G.F. Italiano, in:, 26th Annual ACM-SIAM Symposium on Discrete Algorithms, Society for Industrial and Applied Mathematics, 2014, pp. 785–804. 118752022-08-16T12:36:42Z2024-11-06T12:22:53Z