6 papers · 1 filter
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…
Greedy Completion for Weighted -Spanners
Elad Tzalik
We study -spanners for weighted graphs. We propose a simple greedy completion procedure which starts from a sparse initial graph, and repeatedly fixes pairs of vertices with…
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…
Connectivity Labeling in Faulty Colored Graphs
Asaf Petruschka, Shay Sapir, Elad Tzalik
Fault-tolerant connectivity labelings are schemes that, given an -vertex graph and , produce succinct yet informative labels for the elements of the graph. Gi…
Color Fault-Tolerant Spanners
Asaf Petruschka, Shay Sapir, Elad Tzalik
We initiate the study of spanners in arbitrarily vertex- or edge-colored graphs (with no "legality" restrictions), that are resilient to failures of entire color classes. When a co…