215 citations · 689 across the 60 of their papers we have counts for
7 papers · 1 filter
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…
A Faster Distributed Single-Source Shortest Paths Algorithm
Sebastian Forster, Danupon Nanongkai
We devise new algorithms for the single-source shortest paths (SSSP) problem with non-negative edge weights in the CONGEST model of distributed computing. While close-to-optimal so…
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…
From Gap-ETH to FPT-Inapproximability: Clique, Dominating Set, and More
Parinya Chalermsook, Marek Cygan, Guy Kortsarz +4
We consider questions that arise from the intersection between the areas of polynomial-time approximation algorithms, subexponential-time algorithms, and fixed-parameter tractable…
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…
Distributed Exact Weighted All-Pairs Shortest Paths in Rounds
Chien-Chung Huang, Danupon Nanongkai, Thatchaphol Saranurak
We study computing {\em all-pairs shortest paths} (APSP) on distributed networks (the CONGEST model). The goal is for every node in the (weighted) network to know the distance from…