Yeyuan Chen

collaborators

2 papers

cs.DS2024

The Gap Between Greedy Algorithm and Minimum Multiplicative Spanner

Yeyuan Chen

The greedy algorithm adapted from Kruskal's algorithm is an efficient and folklore way to produce a $k$ -spanner with girth at least $k + 2$ . The greedy algorithm has shown to be `exi…

math.CO2024

Unique-neighbor Expanders with Better Expansion for Polynomial-sized Sets

Yeyuan Chen

A $(d_{1}, d_{2})$ -biregular bipartite graph $G = (L \cup R, E)$ is called left- $(m, I^´)$ unique-neighbor expander iff each subset $S$ of the left vertices with $∣ S ∣ \leq m$ has at least $Î´d…