215 citations · 689 across the 60 of their papers we have counts for
4 papers · 2 filters
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…
Dynamic Minimum Spanning Forest with Subpolynomial Worst-case Update Time
Danupon Nanongkai, Thatchaphol Saranurak, Christian Wulff-Nilsen
We present a Las Vegas algorithm for dynamically maintaining a minimum spanning forest of an -node graph undergoing edge insertions and deletions. Our algorithm guarantees an $O…
New Tools and Connections for Exponential-time Approximation
Nikhil Bansal, Parinya Chalermsook, Bundit Laekhanukit +2
In this paper, we develop new tools and connections for exponential time approximation. In this setting, we are given a problem instance and a parameter , and the goal is to d…
Fully Dynamic Approximate Maximum Matching and Minimum Vertex Cover in 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…