20 citations · 76 across the 29 of their papers we have counts for
4 papers · 1 filter
A Simple Framework for Finding Balanced Sparse Cuts via APSP
Li Chen, Rasmus Kyng, Maximilian Probst Gutenberg +1
We present a very simple and intuitive algorithm to find balanced sparse cuts in a graph via shortest-paths. Our algorithm combines a new multiplicative-weights framework for solvi…
Maximum Flow and Minimum-Cost Flow in Almost-Linear Time
Li Chen, Rasmus Kyng, Yang P. Liu +3
We give an algorithm that computes exact maximum flows and minimum-cost flows on directed graphs with edges and polynomially bounded integral demands, costs, and capacities in…
Maintaining Expander Decompositions via Sparse Cuts
Yiding Hua, Rasmus Kyng, Maximilian Probst Gutenberg +1
In this article, we show that the algorithm of maintaining expander decompositions in graphs undergoing edge deletions directly by removing sparse cuts repeatedly can be made effic…
Hardness Results for Laplacians of Simplicial Complexes via Sparse-Linear Equation Complete Gadgets
Ming Ding, Rasmus Kyng, Maximilian Probst Gutenberg +1
We study linear equations in combinatorial Laplacians of -dimensional simplicial complexes (-complexes), a natural generalization of graph Laplacians. Combinatorial Laplacian…