26 citations · 63 across the 12 of their papers we have counts for
21 papers
Are there graphs whose shortest path structure requires large edge weights?
Aaron Bernstein, Greg Bodwin, Nicole Wein
The aspect ratio of a (positively) weighted graph is the ratio of its maximum edge weight to its minimum edge weight. Aspect ratio commonly arises as a complexity measure in gr…
All-Norm Load Balancing in Graph Streams via the Multiplicative Weights Update Method
Sepehr Assadi, Aaron Bernstein, Zachary Langley
In the weighted load balancing problem, the input is an -vertex bipartite graph between a set of clients and a set of servers, and each client comes with some nonnegative real w…
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 , while the adversary makes changes to the edges of the graph. The goal is to…
Closing the Gap Between Directed Hopsets and Shortcut Sets
Aaron Bernstein, Nicole Wein
For an n-vertex directed graph , a -\emph{shortcut set} is a set of additional edges such that has the same transitive closure…
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 time when edge weights are integral and can be negative. This essential…
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…