5 papers
Deterministic Padded Decompositions and Negative-Weight Shortest Paths
Jason Li
We obtain the first near-linear time deterministic algorithm for negative-weight single-source shortest paths on integer-weighted graphs. Our main ingredient is a deterministic con…
Separator Theorem for Minor-Free Graphs in Linear Time
Ãdouard Bonnet, Tuukka Korhonen, Hung Le +2
The planar separator theorem by Lipton and Tarjan [FOCS '77, SIAM Journal on Applied Mathematics '79] states that any planar graph with vertices has a balanced separator of siz…
Local Sherman's Algorithm for Multi-commodity Flow
Jason Li, Thatchaphol Saranurak
We give the first local algorithm for computing multi-commodity flow and apply it to obtain a -approximate algorithm for computing a -commodity flow on an expander with…
Space Complexity of Minimum Cut Problems in Single-Pass Streams
Matthew Ding, Alexandro Garces, Jason Li +4
We consider the problem of finding a minimum cut of a weighted graph presented as a single-pass stream. While graph sparsification in streams has been intensively studied, the spec…
A Simple and Fast Algorithm for Fair Cuts
Jason Li, Owen Li
We present a simple and faster algorithm for computing fair cuts on undirected graphs, a concept introduced in recent work of Li et al. (SODA 2023). Informally, for any parameter $…