Zihan Tan

collaborators

2 papers

cs.DS2024

Query Complexity of the Metric Steiner Tree Problem

Yu Chen, Sanjeev Khanna, Zihan Tan

We study the query complexity of the metric Steiner Tree problem, where we are given an $n \times n$ metric on a set $V$ of vertices along with a set $T \subseteq V$ of $k$ termina…

cs.DS2024

Almost-Optimal Sublinear Additive Spanners

Zihan Tan, Tianyi Zhang

Given an undirected unweighted graph $G = (V, E)$ on $n$ vertices and $m$ edges, a subgraph $H \subseteq G$ is a spanner of $G$ with stretch function $f: \mathbb{R}_+ \rightarrow \m…