26 citations · 63 across the 12 of their papers we have counts for
Showing 2018Show all
3 papers · 1 filter
cs.DS2018
Towards a Unified Theory of Sparsification for Matching Problems
Sepehr Assadi, Aaron Bernstein
In this paper, we present a construction of a `matching sparsifier', that is, a sparse subgraph of the given graph that preserves large matchings approximately and is robust to mod…
cs.DC2018
Distributed Exact Weighted All-Pairs Shortest Paths in Near-Linear Time
Aaron Bernstein, Danupon Nanongkai
In the {\em distributed all-pairs shortest paths} problem (APSP), every node in the weighted undirected distributed network (the CONGEST model) needs to know the distance from ever…
cs.DS2018★ 26 cited
A Deamortization Approach for Dynamic Spanner and Dynamic Maximal Matching
Aaron Bernstein, Sebastian Forster, Monika Henzinger
Many dynamic graph algorithms have an amortized update time, rather than a stronger worst-case guarantee. But amortized data structures are not suitable for real-time systems, wher…