21 citations · 78 across the 54 of their papers we have counts for
71 papers · 1 filter
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…