10 citations · 54 across the 49 of their papers we have counts for
4 papers · 2 filters
Fast Constructions of Light-Weight Spanners for General Graphs
Michael Elkin, Shay Solomon
To our knowledge, there are only two known algorithms for constructing sparse and light spanners for general graphs. One of them is the greedy algorithm of Althfer et al.…
Fault-Tolerant Spanners for Doubling Metrics: Better and Simpler
Shay Solomon
In STOC'95 Arya et al. (1995) conjectured that for any constant dimensional -point Euclidean space, a $(1+\eps)$-spanner with constant degree, hop-diameter and weigh…
Optimal Euclidean spanners: really short, thin and lanky
Michael Elkin, Shay Solomon
In a seminal STOC'95 paper, titled "Euclidean spanners: short, thin and lanky", Arya et al. devised a construction of Euclidean $(1+\eps)$-spanners that achieves constant degree, d…
Simple Deterministic Algorithms for Fully Dynamic Maximal Matching
Ofer Neiman, Shay Solomon
A maximal matching can be maintained in fully dynamic (supporting both addition and deletion of edges) -vertex graphs using a trivial deterministic algorithm with a worst-case u…