Near-Additive Spanners In Low Polynomial Deterministic CONGEST Time
Michael Elkin, Shaked Matar · 2019
Given a pair of parameters α ≥ 1,β ≥ 0, a subgraph G'=(V,H) of an n-vertex unweighted undirected graph G=(V,E) is called an (α,β)-spanner if for every pair u,ν ∈ V of vertices, we have dG' (u,ν)≤ α dG (u,α)+β. If β=0 the spanner is called a multiplicative α-spanner, and if α = 1+ε, for an arbitrarily small ε>0, the spanner is said to be near-additive.