New pairwise spanners (Q1693988): Difference between revisions

Let \(G=(V,E)\) be an undirected unweighted graph on \(n\) vertices. A subgraph \(H\) of \(G\) is called an (all-pairs) purely additive spanner with stretch \(\beta\) if for every \((u,v)\in V\times V\), \(\operatorname{dist}_H(u,v)\leq \operatorname{dist}_G(u,v)+\beta\). The following problem is considered in this paper. Given \(\mathcal{P}\subseteq V\times V\) then seek a sparse subgraph \(H\) where \(\operatorname{dist}_H(u,v)\leq \operatorname{dist}_G(u,v)+\beta\) for each \((u,v)\in \mathcal{P}\). Such a subgraph is called a pairwise spanner with additive stretch \(\beta\). This paper discusses sparse pairwise spanners with additive stretches \(4\) and \(6\) and also the following special cases \(\mathcal{P}=S\times V\) and \(\mathcal{P}=S\times T\), where \(S\subseteq V\) and \(T\subseteq V\).