215 citations · 318 across the 83 of their papers we have counts for
11 papers · 1 filter
Connectivity Labeling Schemes for Edge and Vertex Faults via Expander Hierarchies
Yaowei Long, Seth Pettie, Thatchaphol Saranurak
We consider the problem of assigning short labels to the vertices and edges of a graph so that given any query with , we can determine whether…
Deterministic Edge Connectivity and Max Flow using Subquadratic Cut Queries
Aditya Anand, Thatchaphol Saranurak, Yunfan Wang
We give the first deterministic algorithm that makes sub-quadratic queries to find the global min-cut of a simple graph in the cut query model. Given an -vertex graph , our a…
Parallel and Distributed Expander Decomposition: Simple, Fast, and Near-Optimal
Daoyuan Chen, Simon Meierhans, Maximilian Probst Gutenberg +1
Expander decompositions have become one of the central frameworks in the design of fast algorithms. For an undirected graph , a near-optimal -expander decomposition is…
Unbreakable Decomposition in Close-to-Linear Time
Aditya Anand, Euiwoong Lee, Jason Li +2
Unbreakable decomposition, introduced by Cygan et al. (SICOMP'19) and Cygan et al. (TALG'20), has proven to be one of the most powerful tools for parameterized graph cut problems i…
Low-Step Multi-Commodity Flow Emulators
Bernhard Haeupler, D Ellis Hershkowitz, Jason Li +2
We introduce the concept of low-step multi-commodity flow emulators for any undirected, capacitated graph. At a high level, these emulators contain approximate multi-commodity flow…
Maximum Flow by Augmenting Paths in Time
Aaron Bernstein, Joakim Blikstad, Thatchaphol Saranurak +1
We present a combinatorial algorithm for computing exact maximum flows in directed graphs with vertices and edge capacities from in time, whi…
Finding Most Shattering Minimum Vertex Cuts of Polylogarithmic Size in Near-Linear Time
Kevin Hua, Daniel Li, Jaewoo Park +1
We show the first near-linear time randomized algorithms for listing all minimum vertex cuts of polylogarithmic size that separate the graph into at least three connected component…
Approximating Small Sparse Cuts
Aditya Anand, Euiwoong Lee, Jason Li +1
We study polynomial-time approximation algorithms for (edge/vertex) Sparsest Cut and Small Set Expansion in terms of , the number of edges or vertices cut in the optimal solutio…
Dynamic Deterministic Constant-Approximate Distance Oracles with Worst-Case Update Time
Bernhard Haeupler, Yaowei Long, Thatchaphol Saranurak
We present a new distance oracle in the fully dynamic setting: given a weighted undirected graph with vertices undergoing both edge insertions and deletions, and an a…
Decremental -Approximate Maximum Eigenvector: Dynamic Power Method
Deeksha Adil, Thatchaphol Saranurak
We present a dynamic algorithm for maintaining -approximate maximum eigenvector and eigenvalue of a positive semi-definite matrix undergoing \emph{decreasing} updates, i…
Cactus Representation of Minimum Cuts: Derandomize and Speed up
Zhongtian He, Shang-En Huang, Thatchaphol Saranurak
Given an undirected weighted graph with vertices and edges, we give the first deterministic -time algorithm for constructing the cactus representation of \emph{…