16 citations · 64 across the 32 of their papers we have counts for
3 papers · 1 filter
Online Edge Coloring Algorithms via the Nibble Method
Sayan Bhattacharya, Fabrizio Grandoni, David Wajc
Nearly thirty years ago, Bar-Noy, Motwani and Naor [IPL'92] conjectured that an online -edge-coloring algorithm exists for -node graphs of maximum degree $Δ=ω(\log n)…
Dynamic Set Cover: Improved Amortized and Worst-Case Update Time
Sayan Bhattacharya, Monika Henzinger, Danupon Nanongkai +1
In the dynamic minimum set cover problem, a challenge is to minimize the update time while guaranteeing close to the optimal approximation factor. (Throughout,…
Coarse-Grained Complexity for Dynamic Algorithms
Sayan Bhattacharya, Danupon Nanongkai, Thatchaphol Saranurak
To date, the only way to argue polynomial lower bounds for dynamic algorithms is via fine-grained complexity arguments. These arguments rely on strong assumptions about specific pr…