29 citations · 31 across the 3 of their papers we have counts for
Showing cs.DSShow all
3 papers · 1 filter
cs.DS2011
iBGP and Constrained Connectivity
Michael Dinitz, Gordon Wilfong
We initiate the theoretical study of the problem of minimizing the size of an iBGP overlay in an Autonomous System (AS) in the Internet subject to a natural notion of correctness d…
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…