Lightweight Near-Additive Spanners
摘要
An \((\alpha ,\beta )\) -spanner of a weighted graph \(G=(V,E)\) , is a subgraph H such that for every \(u,v\in V\) , \(d_G(u,v) \le d_H(u,v)\le \alpha \cdot d_G(u,v)+\beta \) . The main parameters of interest for spanners are their size (number of edges) and their lightness (the ratio between the total weight of H to the weight of a minimum spanning tree). In this paper we focus on near-additive spanners, where \(\alpha =1+\varepsilon \) for arbitrarily small \(\varepsilon >0\) . We show the first construction of light spanners in this setting. Specifically, for any integer parameter \(k\ge 1\) , we obtain an \((1+\varepsilon ,O(k/\varepsilon )^k\cdot W(\cdot ,\cdot ))\) -spanner with lightness \(\widetilde{O}(n^{1/k})\) (where \(W(\cdot ,\cdot )\) indicates for every pair \(u, v \in V\) the heaviest edge in some shortest path between u, v). In addition, we can also bound the number of edges in our spanner by \(O(kn^{1+3/k})\) .