26 citations · 63 across the 12 of their papers we have counts for
5 papers · 1 filter
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 Bounds for Distributed Load Balancing
Sepehr Assadi, Aaron Bernstein, Zachary Langley
In the load balancing problem, the input is an -vertex bipartite graph and a positive weight for each client . The algorithm must assign each client…
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 =…