10 citations · 54 across the 49 of their papers we have counts for
8 papers · 1 filter
Approximating Euclidean Shallow-Light Trees
Hung Le, Shay Solomon, Cuong Than +2
For a weighted graph and a designated source vertex , a spanning tree that simultaneously approximates a shortest-path tree w.r.t. source and a minimum…
Dynamic Set Cover with Worst-Case Recourse
Shay Solomon, Amitai Uzrad
In the dynamic set cover (SC) problem, the input is a dynamic universe of at most elements and a fixed collection of sets, where each element belongs to at most sets an…
Vizing's Theorem in Deterministic Almost-Linear Time
Sepehr Assadi, Soheil Behnezhad, Sayan Bhattacharya +3
Vizing's theorem states that any -vertex -edge graph of maximum degree can be edge colored using at most different colors. Vizing's original proof is easily transl…
Tree-Like Shortcuttings of Trees
Hung Le, Lazar Milenković, Shay Solomon +1
Sparse shortcuttings of trees -- equivalently, sparse 1-spanners for tree metrics with bounded hop-diameter -- have been studied extensively (under different names and settings), s…
Covering the Euclidean Plane by a Pair of Trees
Hung Le, Lazar Milenković, Shay Solomon +1
A {-stretch tree cover} of a metric space , for a parameter , is a collection of trees such that every pair of points has a -stretch path in one of the tr…
Optimal Bounds for Spanners and Tree Covers in Doubling Metrics
An La, Hung Le, Shay Solomon +4
It is known that any -point set in the -dimensional Euclidean space , for , admits: 1) a -spanner with maximum degree and…