Showing 2025Show all
2 papers · 1 filter
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 -fault-tolerant connectivity preserver of a directed -vertex graph is a subgraph such that, for any edge set of size , the strongly co…