20 citations · 72 across the 8 of their papers we have counts for
14 papers
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…
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…
Incremental SSSP for Sparse Digraphs Beyond the Hopset Barrier
Rasmus Kyng, Simon Meierhans, Maximilian Probst Gutenberg
Given a directed, weighted graph undergoing edge insertions, the incremental single-source shortest paths (SSSP) problem asks for the maintenance of approximate distances…
Deterministic Decremental SSSP and Approximate Min-Cost Flow in Almost-Linear Time
Aaron Bernstein, Maximilian Probst Gutenberg, Thatchaphol Saranurak
In the decremental single-source shortest paths problem, the goal is to maintain distances from a fixed source to every vertex in an -edge graph undergoing edge deletion…
Near-Optimal Algorithms for Reachability, Strongly-Connected Components and Shortest Paths in Partially Dynamic Digraphs
Maximilian Probst Gutenberg
In this thesis, we present new techniques to deal with fundamental algorithmic graph problems where graphs are directed and partially dynamic, i.e. undergo either a sequence of edg…
Decremental APSP in Directed Graphs Versus an Adaptive Adversary
Jacob Evald, Viktor Fredslund-Hansen, Maximilian Probst Gutenberg +1
Given a directed graph , undergoing an online sequence of edge deletions with edges in the initial version of and , we consider the problem of maintaini…