Sayan Bhattacharya

activity

20092026

most citedOn Necessary and Sufficient Number of Cops in the Game of Cops and Robber in Multidimensional Grids

16 citations · 64 across the 32 of their papers we have counts for

collaborators

Showing 2017Show all

2 papers · 1 filter

cs.DS2017

Dynamic Algorithms for Graph Coloring

Sayan Bhattacharya, Deeparnab Chakrabarty, Monika Henzinger +1

We design fast dynamic algorithms for proper vertex and edge colorings in a graph undergoing edge insertions and deletions. In the static setting, there are simple linear time algo…

cs.DS2017★ 8 cited

Fully Dynamic Approximate Maximum Matching and Minimum Vertex Cover in $O (lo g^{3} n)$ Worst Case Update Time

Sayan Bhattacharya, Monika Henzinger, Danupon Nanongkai

We consider the problem of maintaining an approximately maximum (fractional) matching and an approximately minimum vertex cover in a dynamic graph. Starting with the seminal paper…

Dynamic Algorithms for Graph Coloring

Fully Dynamic Approximate Maximum Matching and Minimum Vertex Cover in O(log3n) Worst Case Update Time

Fully Dynamic Approximate Maximum Matching and Minimum Vertex Cover in $O (lo g^{3} n)$ Worst Case Update Time