16 citations · 64 across the 32 of their papers we have counts for
3 papers · 1 filter
Fully Dynamic -Coloring in Constant Update Time
Sayan Bhattacharya, Fabrizio Grandoni, Janardhan Kulkarni +2
The problem of (vertex) -coloring a graph of maximum degree has been extremely well-studied over the years in various settings and models. Surprisingly, for the dynamic…
A New Deterministic Algorithm for Dynamic Set Cover
Sayan Bhattacharya, Monika Henzinger, Danupon Nanongkai
We present a deterministic dynamic algorithm for maintaining a -approximate minimum cost set cover with amortized update time, when the input set system…
New Amortized Cell-Probe Lower Bounds for Dynamic Problems
Sayan Bhattacharya, Monika Henzinger, Stefan Neumann
We build upon the recent papers by Weinstein and Yu (FOCS'16), Larsen (FOCS'12), and Clifford et al. (FOCS'15) to present a general framework that gives amortized lower bounds on t…