26 citations · 63 across the 12 of their papers we have counts for
5 papers · 1 filter
Coresets Meet EDCS: Algorithms for Matching and Vertex Cover on Massive Graphs
Sepehr Assadi, MohammadHossein Bateni, Aaron Bernstein +2
As massive graphs become more prevalent, there is a rapidly growing need for scalable algorithms that solve classical graph problems, such as maximum matching and minimum vertex co…
Online Bipartite Matching with Amortized Replacements
Aaron Bernstein, Jacob Holm, Eva Rotenberg
In the online bipartite matching problem with replacements, all the vertices on one side of the bipartition are given, and the vertices on the other side arrive one by one with all…
Deterministic Partially Dynamic Single Source Shortest Paths in Weighted Graphs
Aaron Bernstein
In this paper we consider the decremental single-source shortest paths (SSSP) problem, where given a graph and a source node the goal is to maintain shortest distances betw…
General Bounds for Incremental Maximization
Aaron Bernstein, Yann Disser, Martin Groß
We propose a theoretical framework to capture incremental solutions to cardinality constrained maximization problems. The defining characteristic of our framework is that the cardi…
Distance-preserving graph contractions
Aaron Bernstein, Karl Däubel, Yann Disser +3
Compression and sparsification algorithms are frequently applied in a preprocessing step before analyzing or optimizing large networks/graphs. In this paper we propose and study a…