Benyu Wang

collaborators

3 papers

cs.DS2025

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…

cs.DS2025

Near-Optimal Fault-Tolerant Strong Connectivity Preservers

Gary Hoppenworth, Thatchaphol Saranurak, Benyu Wang

A $k$ -fault-tolerant connectivity preserver of a directed $n$ -vertex graph $G$ is a subgraph $H$ such that, for any edge set $F \subseteq E (G)$ of size $∣ F ∣ \leq k$ , the strongly co…

cs.DS2024

Undirected 3-Fault Replacement Path in Nearly Cubic Time

Shucheng Chi, Ran Duan, Benyu Wang +1

Given a graph $G = (V, E)$ and two vertices $s, t \in V$ , the $f$ -fault replacement path ( $f$ FRP) problem computes for every set of edges $F$ where $∣ F ∣ \leq f$ , the distance from $s$ to…