2 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…