A. Bernstein

activity

20152023

most citedA Deamortization Approach for Dynamic Spanner and Dynamic Maximal Matching

26 citations · 63 across the 12 of their papers we have counts for

collaborators

Showing 2022Show all

3 papers · 1 filter

cs.DS2022★ 1 cited

Decremental Matching in General Graphs

Sepehr Assadi, Aaron Bernstein, Aditi Dudeja

We consider the problem of maintaining an approximate maximum integral matching in a dynamic graph $G$ , while the adversary makes changes to the edges of the graph. The goal is to…

cs.DS2022

Closing the Gap Between Directed Hopsets and Shortcut Sets

Aaron Bernstein, Nicole Wein

For an n-vertex directed graph $G = (V, E)$ , a $β$ -\emph{shortcut set} $H$ is a set of additional edges $H \subseteq V \times V$ such that $G \cup H$ has the same transitive closure…

cs.DS2022★ 2 cited

Negative-Weight Single-Source Shortest Paths in Near-linear Time

Aaron Bernstein, Danupon Nanongkai, Christian Wulff-Nilsen

We present a randomized algorithm that computes single-source shortest paths (SSSP) in $O (m lo g^{8} (n) lo g W)$ time when edge weights are integral and can be negative. This essential…