3 papers
cs.DS2024
Almost-Linear Time Algorithms for Decremental Graphs: Min-Cost Flow and More via Duality
Jan van den Brand, Li Chen, Rasmus Kyng +4
We give the first almost-linear total time algorithm for deciding if a flow of cost at most still exists in a directed graph, with edge costs and capacities, undergoing decreme…
cs.DS2023
Almost-Linear Time Algorithms for Incremental Graphs: Cycle Detection, SCCs, - Shortest Path, and Minimum-Cost Flow
Li Chen, Rasmus Kyng, Yang P. Liu +2
We give the first almost-linear time algorithms for several problems in incremental graphs including cycle detection, strongly connected component maintenance, - shortest pat…
cs.DS2023
Incremental Approximate Maximum Flow on Undirected Graphs in Subpolynomial Update Time
Jan van den Brand, Li Chen, Rasmus Kyng +5
We provide an algorithm which, with high probability, maintains a -approximate maximum flow on an undirected graph undergoing -edge additions in amortized $m^{o(1)} ε^{-3…