215 citations · 318 across the 83 of their papers we have counts for
10 papers · 1 filter
Directed Global Minimum Cut in Almost-Linear Time
Henry Fleischmann, Jason Li, Thatchaphol Saranurak +1
We give a randomized reduction from global minimum cut in a directed graph with vertices and weighted edges to maximum-flow computations on graphs of total size $\widetilde…
Deterministic Edge-Fault-Tolerant Connectivity Labeling Schemes with Nearly Optimal Label Size
Yaowei Long, Seth Pettie, Thatchaphol Saranurak
For an undirected graph and a fault bound , an edge-fault-tolerant connectivity labeling scheme assigns short labels to vertices and edges, so that for any vertex pa…
Connectivity Oracles Under Vertex Failures via a Simple and Fast Low-Degree Steiner Forest Decomposition
Sayan Bhattacharya, Ermiya Farokhnejad, Thatchaphol Saranurak +1
We study the low-degree Steiner forest decomposition. Given a graph and a terminal set , the standard decomposition returns a set of size at…
Incremental Directed Minimum Cut by Dynamizing Gabow's Algorithm
Thatchaphol Saranurak, Kaiyang Xie, Zhaienhe Zhou
We give the first incremental algorithm for directed global minimum cut. Given a directed graph with vertices undergoing edge insertions, our deterministic algorithm explic…
Minimum Degree Spanning Tree: -Approximation in Near-Linear Time
Sayan Bhattacharya, Ermiya Farokhnejad, Thatchaphol Saranurak +1
The minimum degree spanning tree problem is a classic NP-hard problem whose optimal approximation guarantee was established since the early 1990s: Fürer and Raghavachari [FR92] gav…
Connectivity Oracle Under Vertex Failures by Shortcutting Unbreakable Decomposition
Xizhe Li, Yaowei Long, David Pidugu +2
We give an improved connectivity oracle under vertex failures. After a set of vertices fails, our oracle performs an -time update independent of the graph size , a…
Parallel Reachability and Shortest Paths on Non-sparse Digraphs: Near-linear Work and Sub-square-root Depth
Vikrant Ashvinkumar, Aaron Bernstein, Maximilian Probst Gutenberg +1
We present parallel algorithms for computing single-source reachability and shortest paths on directed -vertex -edge graphs using near-linear work and $o(\sqrt…
DAG Projections: Reducing Distance and Flow Problems to DAGs
Bernhard Haeupler, Yonggang Jiang, Thatchaphol Saranurak
We show that every directed graph with vertices and edges admits a directed acyclic graph (DAG) with edges, called a DAG projection, that can either $(1+1/…
A Constant-Approximation Distance Labeling Scheme under Polynomially Many Edge Failures
Bernhard Haeupler, Yaowei Long, Antti Roeyskoe +1
A fault-tolerant distance labeling scheme assigns a label to each vertex and edge of an undirected weighted graph with vertices so that, for any edge set of size $|F| \…
Expander Decomposition with Almost Optimal Overhead
Nikhil Bansal, Arun Jambulapati, Thatchaphol Saranurak
We present the first polynomial-time algorithm for computing a near-optimal \emph{flow}-expander decomposition. Given a graph and a parameter , our algorithm removes at most…