3 papers
cs.DS2026
Dynamic Rank, Basis, and Matching
Jan van den Brand, Vishal Kumar, Daniel J. Zhang
We study dynamic algorithms for maintaining fundamental algebraic properties of matrices, specifically, rank, basis, and full-rank submatrices, with applications to maximum matchin…
cs.DS2026
Computing Flows in Subquadratic Space
Jan van den Brand, Zhao Song, Albert Weng
Space complexity is a critical factor in various computational models, including streaming, parallel/distributed computing, and communication complexity. We study the space complex…
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…