9 citations · 15 across the 4 of their papers we have counts for
9 papers · 1 filter
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…
Deterministic Decremental Reachability, SCC, and Shortest Paths via Directed Expanders and Congestion Balancing
Aaron Bernstein, Maximilian Probst Gutenberg, Thatchaphol Saranurak
Let be a weighted, digraph subject to a sequence of adversarial edge deletions. In the decremental single-source reachability problem (SSR), we are given a fixed sour…
Improved Bound for Matching in Random-Order Streams
Aaron Bernstein
We study the problem of computing an approximate maximum cardinality matching in the semi-streaming model when edges arrive in a \emph{random} order. In the semi-streaming model, t…
Fully-Dynamic Graph Sparsifiers Against an Adaptive Adversary
Aaron Bernstein, Jan van den Brand, Maximilian Probst Gutenberg +4
Designing dynamic graph algorithms against an adaptive adversary is a major goal in the field of dynamic graph algorithms. While a few such algorithms are known for spanning trees,…
Near-Optimal Decremental SSSP in Dense Weighted Digraphs
Aaron Bernstein, Maximilian Probst Gutenberg, Christian Wulff-Nilsen
In the decremental Single-Source Shortest Path problem (SSSP), we are given a weighted directed graph undergoing edge deletions and a source vertex ; let $n =…
Decremental Strongly-Connected Components and Single-Source Reachability in Near-Linear Time
Aaron Bernstein, Maximilian Probst, Christian Wulff-Nilsen
Computing the Strongly-Connected Components (SCCs) in a graph is known to take only time using an algorithm by Tarjan from 1972[SICOMP 72] where , $n=…