29 citations · 51 across the 3 of their papers we have counts for
3 papers
cs.DS2011★ 29 cited
Fault-Tolerant Spanners: Better and Simpler
Michael Dinitz, Robert Krauthgamer
A natural requirement of many distributed structures is fault-tolerance: after some failures, whatever remains from the structure should still be effective for whatever remains fro…
cs.DS2010★ 2 cited
Directed Spanners via Flow-Based Linear Programs
Michael Dinitz, Robert Krauthgamer
We examine directed spanners through flow-based linear programming relaxations. We design an -approximation algorithm for the directed -spanner problem that works fo…
cs.DS2010★ 20 cited
Streaming Algorithms from Precision Sampling
Alexandr Andoni, Robert Krauthgamer, Krzysztof Onak
A technique introduced by Indyk and Woodruff [STOC 2005] has inspired several recent advances in data-stream algorithms. We show that a number of these results follow easily from t…