Tianyi Zhang

activity

20242026

collaborators

11 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.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.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.DS2025

Approximate Light Spanners in Planar Graphs

Hung Le, Shay Solomon, Cuong Than +2

In their seminal paper, AlthÃ¶fer et al. (DCG 1993) introduced the {\em greedy spanner} and showed that, for any weighted planar graph $G$ , the weight of the greedy $(1 + I^µ)$ -spanne…

cs.DS2025

Vizing's Theorem in Deterministic Almost-Linear Time

Sepehr Assadi, Soheil Behnezhad, Sayan Bhattacharya +3

Vizing's theorem states that any $n$ -vertex $m$ -edge graph of maximum degree $I^$ can be edge colored using at most $I^ + 1$ different colors. Vizing's original proof is easily tran…

cs.DS2025

Vizing's Theorem in Near-Linear Time

Sepehr Assadi, Soheil Behnezhad, Sayan Bhattacharya +3

Vizing's theorem states that any $n$ -vertex $m$ -edge graph of maximum degree $I^$ can be edge colored using at most $I^ + 1$ different colors [Vizing, 1964]. Vizing's original proof…