10 citations · 54 across the 49 of their papers we have counts for
9 papers · 1 filter
Sparse Euclidean Spanners with Tiny Diameter: A Tight Lower Bound
Hung Le, Lazar Milenkovic, Shay Solomon
In STOC'95 [ADMSS'95] Arya et al. showed that any set of points in admits a -spanner with hop-diameter at most 2 (respectively, 3) and edges…
A Unified Framework of Light Spanners II: Fine-Grained Optimality
Hung Le, Shay Solomon
Seminal works on light spanners over the years provide spanners with optimal lightness in various graph classes, such as in general graphs, Euclidean spanners, and minor-free graph…
Maintaining an EDCS in General Graphs: Simpler, Density-Sensitive and with Worst-Case Time Bounds
Fabrizio Grandoni, Chris Schwiegelshohn, Shay Solomon +1
In their breakthrough ICALP'15 paper, Bernstein and Stein presented an algorithm for maintaining a -approximate maximum matching in fully dynamic {\em bipartite} graphs wi…
Near-Optimal Spanners for General Graphs in (Nearly) Linear Time
Hung Le, Shay Solomon
Let be a weighted undirected graph on vertices and edges, let be any integer, and let be any parameter. We present the following…
Can't See The Forest for the Trees: Navigating Metric Spaces by Bounded Hop-Diameter Spanners
Omri Kahalon, Hung Le, Lazar Milenkovic +1
Spanners for metric spaces have been extensively studied, both in general metrics and in restricted classes, perhaps most notably in low-dimensional Euclidean spaces -- due to thei…
Towards a Unified Theory of Light Spanners I: Fast (Yet Optimal) Constructions
Hung Le, Shay Solomon
Seminal works on light spanners over the years provide spanners with optimal lightness in various graph classes, such as in general graphs, Euclidean spanners, and minor-free graph…