6 papers
Directed Global Minimum Cut in Almost-Linear Time
Henry Fleischmann, Jason Li, Thatchaphol Saranurak +1
We give a randomized reduction from global minimum cut in a directed graph with vertices and weighted edges to maximum-flow computations on graphs of total size $\widetilde…
Faster Weak Expander Decompositions and Approximate Max Flow
Henry Fleischmann, George Z. Li, Jason Li
We give faster algorithms for weak expander decompositions and approximate max flow on undirected graphs. First, we show that it is possible to "warm start" the cut-matching game w…
Reviving Thorup's Shortcut Conjecture
Aaron Bernstein, Henry Fleischmann, Maximilian Probst Gutenberg +7
We aim to revive Thorup's conjecture [Thorup, WG'92] on the existence of reachability shortcuts with ideal size-diameter tradeoffs. Thorup originally asked whether, given any graph…
Fast Algorithms for Graph Arboricity and Related Problems
Ruoxu Cen, Henry Fleischmann, George Z. Li +2
We give an algorithm for finding the arboricity of a weighted, undirected graph, defined as the minimum number of spanning forests that cover all edges of the graph, in $\sqrt{n} m…
Improved Directed Expander Decompositions
Henry Fleischmann, George Z. Li, Jason Li
We obtain faster expander decomposition algorithms for directed graphs, matching the guarantees of Saranurak and Wang (SODA 2019) for expander decomposition on undirected graphs. O…
Beyond Symmetry in Repeated Games with Restarts
Henry Fleischmann, Kiriaki Fragkia, Ratip Emin Berker
Infinitely repeated games support equilibrium concepts beyond those present in one-shot games (e.g., cooperation in the prisoner's dilemma). Nonetheless, repeated games fail to cap…