7 papers · 1 filter
Bellman-Ford in Almost-Linear Time
Isaac M. Hair, George Z. Li, Jason Li +1
We consider the single-source shortest paths problem on a directed graph with real-valued (possibly negative) edge weights and solve this problem in time.
Improved Strongly Polynomial Work-Span Tradeoffs for Directed Single Source Shortest Paths
Isaac M. Hair, George Z. Li, Jason Li +1
We revisit the single-source shortest paths (SSSP) problem on directed graphs with nonnegative real weights and give a deterministic parallel algorithm with $O(n^{1+o(1)}t^2 + m^{1…
Balancing Weights, Directed Sparsification, and Augmenting Paths
Jason Li
We present a randomized augmenting paths-based algorithm to compute the maximum flow in a directed, uncapacitated graph in almost time, matching the algorithm of Karger and…
Bellman-Ford in Almost-Linear Time for Dense Graphs
George Z. Li, Jason Li, Junkai Zhang
We consider the single-source shortest paths problem on a directed graph with real-valued (possibly negative) edge weights and solve this problem in time by refining t…
Shortcutting for Negative-Weight Shortest Path
George Z. Li, Jason Li, Satish Rao +1
Consider the single-source shortest paths problem on a directed graph with real-valued edge weights. We solve this problem in time, improving on prior work…
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…