Almost-Optimal Sublinear Additive Spanners
Zihan Tan, Tianyi Zhang · 2023
Given an undirected unweighted graph G = (V, E) on n vertices and m edges, a subgraph H⊆ G is a spanner of G with stretch function f: ℝ+ → ℝ+, iff for every pair s, t of vertices in V, distH(s, t)≤ f(distG(s, t)). When f(d) = d + o(d), H is called a sublinear additive spanner; when f(d) = d + o(n), H is called an additive spanner, and f(d) − d is usually called the additive stretch of H.