Fast Construction of 4-Additive Spanners
share
A k-additive spanner of a graph is a subgraph that preserves the distance between any two nodes up to a total additive error of +k. Efficient algorithms have been devised for constructing 2 [Aingworth et al. SIAM '99], 6 [Baswana et al. ACM '10, Woodruff ICALP '13], and 8-additive spanners [Knudsen '17], but efficiency hasn't been studied for 4-additive spanner constructions. In this paper we present a modification of Chechik's 4-additive spanner construction [Chechik SODA '13] that produces a 4-additive spanner on O(n^7/5) edges, with an improved runtime of O(mn^3/5) from O(mn).
READ FULL TEXT