Shay Solomon

collaborators

12 papers

cs.CG2026

Improved Euclidean Shallow Light Trees

Hung Le, Shay Solomon, Cuong Than +3

For parameters $α, β \geq 1$ , a spanning tree $T$ of a weighted graph $G$ rooted at a designated vertex $r$ is called an $(α, β)$ -shallow-light tree (SLT) if (i) for every vertex $v$ ,…

cs.DS2026

Dynamic Dominating Set in Uniformly Sparse Graphs

Anton Bukov, Shay Solomon

In the dynamic {\em minimum dominating set (MDS)} problem, the goal is to efficiently maintain an approximate MDS in an $n$ -vertex graph with vertex costs in $[1/ C, 1]$ undergoing e…

cs.CG2026

Optimal Bounds for Spanners and Tree Covers in Doubling Metrics

An La, Hung Le, Shay Solomon +4

It is known that any $n$ -point set in the $d$ -dimensional Euclidean space $R^{d}$ , for $d = O (1)$ , admits: 1) a $(1 + I^µ)$ -spanner with maximum degree $O ~ (I^µ^{- d + 1})$ a…

cs.DS2025

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…

cs.CG2025

Approximating Euclidean Shallow-Light Trees

Hung Le, Shay Solomon, Cuong Than +2

For a weighted graph $G = (V, E, w)$ and a designated source vertex $s \in V$ , a spanning tree that simultaneously approximates a shortest-path tree w.r.t. source $s$ and a minimum…

cs.CG2025

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…