3 citations · 5 across the 5 of their papers we have counts for
5 papers
Nibbling at Long Cycles: Dynamic (and Static) Edge Coloring in Optimal Time
Sayan Bhattacharya, Martín Costa, Nadav Panski +1
We consider the problem of maintaining a -edge coloring in a dynamic graph with nodes and maximum degree at most . The state-of-the-art update time is $O_ε(\text…
Fully Dynamic -Clustering in Update Time
Sayan Bhattacharya, Martín Costa, Silvio Lattanzi +1
We present a -approximate fully dynamic algorithm for the -median and -means problems on metric spaces with amortized update time and worst-case query tim…
Dynamic Algorithms for Packing-Covering LPs via Multiplicative Weight Updates
Sayan Bhattacharya, Peter Kiss, Thatchaphol Saranurak
In the dynamic linear program (LP) problem, we are given an LP undergoing updates and we need to maintain an approximately optimal solution. Recently, significant attention (e.g.,…
Deterministic Fully Dynamic Approximate Vertex Cover and Fractional Matching in Amortized Update Time
Sayan Bhattacharya, Deeparnab Chakrabarty, Monika Henzinger
We consider the problems of maintaining an approximate maximum matching and an approximate minimum vertex cover in a dynamic graph undergoing a sequence of edge insertions/deletion…
Deterministic Fully Dynamic Data Structures for Vertex Cover and Matching
Sayan Bhattacharya, Monika Henzinger, Giuseppe F. Italiano
We present the first deterministic data structures for maintaining approximate minimum vertex cover and maximum matching in a fully dynamic graph , with and $|…