16 citations · 64 across the 32 of their papers we have counts for
3 papers · 1 filter
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…
New Deterministic Approximation Algorithms for Fully Dynamic Matching
Sayan Bhattacharya, Monika Henzinger, Danupon Nanongkai
We present two deterministic dynamic algorithms for the maximum matching problem. (1) An algorithm that maintains a -approximate maximum matching in general graphs with $O(\…
Design of Dynamic Algorithms via Primal-Dual Method
Sayan Bhattacharya, Monika Henzinger, Giuseppe F. Italiano
We develop a dynamic version of the primal-dual method for optimization problems, and apply it to obtain the following results. (1) For the dynamic set-cover problem, we maintain a…