New Greedy Spanners and Applications

Elizaveta Popova, Elad Tzalik

We present a simple greedy procedure to compute an $(\hat{I}\pm ,{\hat{I}}^2)$-spanner for a graph $G$. We then show that this procedure is useful for building fault-tolerant spanners, as well as sp…