215 citations · 318 across the 83 of their papers we have counts for
16 papers · 1 filter
Approximating Directed Minimum Cut and Arborescence Packing via Directed Expander Hierarchies
Yonggang Jiang, Yaowei Long, Thatchaphol Saranurak +1
We give almost-linear-time algorithms for approximating rooted minimum cut and maximum arborescence packing in directed graphs, two problems that are dual to each other [Edm73]. Mo…
Deterministic Negative-Weight Shortest Paths in Nearly Linear Time via Path Covers
Bernhard Haeupler, Yonggang Jiang, Thatchaphol Saranurak
We present the first deterministic nearly-linear time algorithm for single-source shortest paths with negative edge weights on directed graphs: given a directed graph with …
Disjoint Paths in Expanders in Deterministic Almost-Linear Time via Hypergraph Perfect Matching
Matija Bucić, Zhongtian He, Shang-En Huang +1
We design efficient deterministic algorithms for finding short edge-disjoint paths in expanders. Specifically, given an -vertex -edge expander of conductance and mini…
Reviving Thorup's Shortcut Conjecture
Aaron Bernstein, Henry Fleischmann, Maximilian Probst Gutenberg +7
We aim to revive Thorup's conjecture [Thorup, WG'92] on the existence of reachability shortcuts with ideal size-diameter tradeoffs. Thorup originally asked whether, given any graph…
Parallel -Approximate Multi-Commodity Mincost Flow in Almost Optimal Depth and Work
Bernhard Haeupler, Yonggang Jiang, Yaowei Long +2
We present a parallel algorithm for computing -approximate mincost flow on an undirected graph with edges, where capacities and costs are assigned to both edges and vert…
Separations between Oblivious and Adaptive Adversaries for Natural Dynamic Graph Problems
Aaron Bernstein, Sayan Bhattacharya, Nick Fischer +2
We establish the first update-time separation between dynamic algorithms against oblivious adversaries and those against adaptive adversaries in natural dynamic graph problems, bas…
Combinatorial Maximum Flow via Weighted Push-Relabel on Shortcut Graphs
Aaron Bernstein, Joakim Blikstad, Jason Li +2
We give a combinatorial algorithm for computing exact maximum flows in directed graphs with vertices and edge capacities from in time,…
Near-Optimal Fault-Tolerant Strong Connectivity Preservers
Gary Hoppenworth, Thatchaphol Saranurak, Benyu Wang
A -fault-tolerant connectivity preserver of a directed -vertex graph is a subgraph such that, for any edge set of size , the strongly co…
Reducing Shortcut and Hopset Constructions to Shallow Graphs
Bernhard Haeupler, Yonggang Jiang, Thatchaphol Saranurak
We introduce a blackbox framework that simplifies all known parallel algorithms with near-linear work for single-source reachability and shortest paths in directed graphs. Specific…
Deterministic Almost-Linear-Time Gomory-Hu Trees
Amir Abboud, Rasmus Kyng, Jason Li +5
Given an -edge, undirected, weighted graph , a Gomory-Hu tree (Gomory and Hu, 1961) is a tree over the vertex set such that all-pairs mincuts in are prese…
All-Subsets Important Separators with Applications to Sample Sets, Balanced Separators and Vertex Sparsifiers in Directed Graphs
Aditya Anand, Euiwoong Lee, Jason Li +1
Given a directed graph with vertices and edges, a parameter and two disjoint subsets , we show that the number of all-subsets important separato…
Deterministic Dynamic Maximal Matching in Sublinear Update Time
Aaron Bernstein, Sayan Bhattacharya, Peter Kiss +1
We give a fully dynamic deterministic algorithm for maintaining a maximal matching of an -vertex graph in amortized update time. This breaks the long-standi…
Expander Pruning with Polylogarithmic Worst-Case Recourse and Update Time
Simon Meierhans, Maximilian Probst Gutenberg, Thatchaphol Saranurak
Expander graphs are known to be robust to edge deletions in the following sense: for any online sequence of edge deletions to an -edge graph that is…
Length-Constrained Directed Expander Decomposition and Length-Constrained Vertex-Capacitated Flow Shortcuts
Bernhard Haeupler, Yaowei Long, Thatchaphol Saranurak +1
We show the existence of length-constrained expander decomposition in directed graphs and undirected vertex-capacitated graphs. Previously, its existence was shown only in undirect…
Deterministic Vertex Connectivity via Common-Neighborhood Clustering and Pseudorandomness
Yonggang Jiang, Chaitanya Nalam, Thatchaphol Saranurak +1
We give a deterministic algorithm for computing a global minimum vertex cut in a vertex-weighted graph vertices and edges in time. This breaks the long-sta…
Local Sherman's Algorithm for Multi-commodity Flow
Jason Li, Thatchaphol Saranurak
We give the first local algorithm for computing multi-commodity flow and apply it to obtain a -approximate algorithm for computing a -commodity flow on an expander with $…