3 papers
cs.DS2025
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…
cs.DS2025
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…
cs.DS2025
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…