Caleb Robelle

collaborators

Showing cs.DSShow all

3 papers · 1 filter

cs.DS2021

Partially Optimal Edge Fault-Tolerant Spanners

Greg Bodwin, Michael Dinitz, Caleb Robelle

Recent work has established that, for every positive integer $k$ , every $n$ -node graph has a $(2 k - 1)$ -spanner on $O (f^{1 - 1/ k} n^{1 + 1/ k})$ edges that is resilient to $f$ edge or ver…

cs.DS2020

Optimal Vertex Fault-Tolerant Spanners in Polynomial Time

Greg Bodwin, Michael Dinitz, Caleb Robelle

Recent work has pinned down the existentially optimal size bounds for vertex fault-tolerant spanners: for any positive integer $k$ , every $n$ -node graph has a $(2 k - 1)$ -spanner on $…

cs.DS2020

Efficient and Simple Algorithms for Fault Tolerant Spanners

Michael Dinitz, Caleb Robelle

It was recently shown that a version of the greedy algorithm gives a construction of fault-tolerant spanners that is size-optimal, at least for vertex faults. However, the algorith…