1 citations · 1 across the 2 of their papers we have counts for
6 papers
A Dynamic Shortest Paths Toolbox: Low-Congestion Vertex Sparsifiers and their Applications
Rasmus Kyng, Simon Meierhans, Maximilian Probst Gutenberg
We present a general toolbox, based on new vertex sparsifiers, for designing data structures to maintain shortest paths in dynamic graphs. In an -edge graph undergoing edge inse…
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…
A Deterministic Almost-Linear Time Algorithm for Minimum-Cost Flow
Jan van den Brand, Li Chen, Rasmus Kyng +5
We give a deterministic time algorithm that computes exact maximum flows and minimum-cost flows on directed graphs with edges and polynomially bounded integral dem…
Robust and Practical Solution of Laplacian Equations by Approximate Elimination
Yuan Gao, Rasmus Kyng, Daniel A. Spielman
We introduce a new algorithm and software for solving linear equations in symmetric diagonally dominant matrices with non-positive off-diagonal entries (SDDM matrices), including L…
Derandomizing Directed Random Walks in Almost-Linear Time
Rasmus Kyng, Simon Meierhans, Maximilian Probst Gutenberg
In this article, we present the first deterministic directed Laplacian L systems solver that runs in time almost-linear in the number of non-zero entries of L. Previous reductions…
A Framework for Analyzing Resparsification Algorithms
Rasmus Kyng, Jakub Pachocki, Richard Peng +1
A spectral sparsifier of a graph is a sparser graph that approximately preserves the quadratic form of , i.e. for all vectors , , where $…