The Sparsest Additive Spanner via Multiple Weighted BFS Trees

Keren Censor-Hillel, Ami Paz, Noam Ravid

Spanners are fundamental graph structures that sparsify graphs at the cost of small stretch. In particular, in recent years, many sequential algorithms constructing additive all-pa…