2 citations · 3 across the 12 of their papers we have counts for
3 papers · 1 filter
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…
Parallel -Approximate Multi-Commodity Mincost Flow in Almost Optimal Depth and Work
Bernhard Haeupler, Yonggang Jiang, Yaowei Long +2
We present a parallel algorithm for computing -approximate mincost flow on an undirected graph with edges, where capacities and costs are assigned to both edges and vert…
Length-Constrained Directed Expander Decomposition and Length-Constrained Vertex-Capacitated Flow Shortcuts
Bernhard Haeupler, Yaowei Long, Thatchaphol Saranurak +1
We show the existence of length-constrained expander decomposition in directed graphs and undirected vertex-capacitated graphs. Previously, its existence was shown only in undirect…