4 papers
New Greedy Spanners and Applications
Elizaveta Popova, Elad Tzalik
We present a simple greedy procedure to compute an -spanner for a graph . We then show that this procedure is useful for building fault-tolerant spanners, as well as span…
Hypercube minor-universality
Itai Benjamini, Or Kalifa, Elad Tzalik
A graph is -minor-universal if every graph with at most edges (and no isolated vertices) is a minor of . We prove that the -dimensional hypercube, , is $Ω\lef…
Connectivity Certificate against Bounded-Degree Faults: Simpler, Better and Supporting Vertex Faults
Merav Parter, Elad Tzalik
An -edge (or vertex) connectivity certificate is a sparse subgraph that maintains connectivity under the failure of at most edges (or vertices). It is well known that any $n…
Parks and Recreation: Color Fault-Tolerant Spanners Made Local
Merav Parter, Asaf Petruschka, Shay Sapir +1
We provide new algorithms for constructing spanners of arbitrarily edge- or vertex-colored graphs, that can endure up to failures of entire color classes. The failure of even a…