215 citations · 318 across the 83 of their papers we have counts for
9 papers · 1 filter
Deterministic Algorithms for Decremental Shortest Paths via Layered Core Decomposition
Julia Chuzhoy, Thatchaphol Saranurak
In the decremental single-source shortest paths (SSSP) problem, the input is an undirected graph with vertices and edges undergoing edge deletions, together with…
Deterministic Decremental Reachability, SCC, and Shortest Paths via Directed Expanders and Congestion Balancing
Aaron Bernstein, Maximilian Probst Gutenberg, Thatchaphol Saranurak
Let be a weighted, digraph subject to a sequence of adversarial edge deletions. In the decremental single-source reachability problem (SSR), we are given a fixed sour…
Bipartite Matching in Nearly-linear Time on Moderately Dense Graphs
Jan van den Brand, Yin-Tat Lee, Danupon Nanongkai +5
We present an -time randomized algorithm for maximum cardinality bipartite matching and related problems (e.g. transshipment, negative-weight shortest paths, a…
A Simple Deterministic Algorithm for Edge Connectivity
Thatchaphol Saranurak
We show a deterministic algorithm for computing edge connectivity of a simple graph with edges in time. Although the fastest deterministic algorithm by Henzinger,…
Deterministic Distributed Expander Decomposition and Routing with Applications in Distributed Derandomization
Yi-Jun Chang, Thatchaphol Saranurak
There is a recent exciting line of work in distributed graph algorithms in the model that exploit expanders. All these algorithms so far are based on two tools:…
Fast Dynamic Cuts, Distances and Effective Resistances via Vertex Sparsifiers
Li Chen, Gramoz Goranci, Monika Henzinger +2
We present a general framework of designing efficient dynamic approximate algorithms for optimization on undirected graphs. In particular, we develop a technique that, given any pr…
The Expander Hierarchy and its Applications to Dynamic Graph Algorithms
Gramoz Goranci, Harald Räcke, Thatchaphol Saranurak +1
We introduce a notion for hierarchical graph clustering which we call the expander hierarchy and show a fully dynamic algorithm for maintaining such a hierarchy on a graph with …
Fully-Dynamic Graph Sparsifiers Against an Adaptive Adversary
Aaron Bernstein, Jan van den Brand, Maximilian Probst Gutenberg +4
Designing dynamic graph algorithms against an adaptive adversary is a major goal in the field of dynamic graph algorithms. While a few such algorithms are known for spanning trees,…
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…