New pairwise spanners (Q1693988): Difference between revisions
From MaRDI portal
Latest revision as of 01:54, 15 July 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | New pairwise spanners |
scientific article |
Statements
New pairwise spanners (English)
0 references
1 February 2018
0 references
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\).
0 references
undirected graphs
0 references
shortest paths, approximate distances, additive stretch, spanners
0 references
0 references
0 references