For an unweighted graph G = (V, E), G′ = (V, E′) is a subgraph if E′ ⊆ E, and G″ = (V″, E″, ω) is a Steiner graph if V ⊆ V″, and for any pair of vertices u, w ∈ V, the distance bet-ween them in G″(denoted dG″, (u, w)) is at least the distance between them in G (denoted da(u, w)).In this paperwe introduce the notion of distance preserver. A subgraph (resp., Steiner graph) G′ of a graph G is a subgraph (resp., Steiner) D-preserver of G if for every pair of vertices u, w ∈ V with dG(u, w) ≥ D, dG′, (u, w) = dG(u, w). We show that anygraph (resp., digraph) has a subgraph D-preserver with at most O(n2/D) edges (resp., arcs), and there are graphs and digraphs for which any undirected Steiner D-preserver contains Ω(n2/D) edges. However, we show that if one allows a directed Steiner (or, shortly, diS-teiner) D-preserver, then these bounds can be improved. Specifically, we show that for any graph or digraph there exists a diSteiner D-preserver with O(n2.log D/D.log n arcs, and that this result is tight up to a constant factor.We also study D-preserving distance labeling schemes, that are labeling schemes that guarantee precise calculation ofdistances between pairs of vertices that are at distance at least D one from another. We show that there exists a D-preserving labeling scheme with labels of size O(n/Dlog2n), and that labels of size Ω(n/D log D) are required for any D-preserving labeling scheme.Finally, we study additive spanners. A subgraph G′ of an undirected graph G = (V, E) is its additive β-spanner if for any pair of vertices u, w ∈ V, dG′, (u, w) ≤ dG(u, w)+β. It is known that for any n-vertex graph there exists an additive 2-spanner with O(n3/2) edges, and an additive Steiner 4-spanner with O(n4/3) edges. However, no construction of additive spanners with o(n3/2) edges or Steiner additive spanners with o(n4/3) edges are known so far. We devise a construction of additive O(21/Δn(1-Δ)[1/Δ]--2/[1/Δ]--1)-spanner with O(n1+Δ) edges for any graph and any Δ 0.
展开▼
机译：对于非加权图 G =（ V，E ），G′=（ V ， E '）为如果E'⊆ E 且G''=（ V ''，E''，ω）的子图是Steiner图，如果 V ⊆V ”，并且对于任何一对顶点 u ， w ∈ V ，它们之间的距离在G''中（表示为 d G'' ，（ u ， w ））至少是它们之间在 G 中的距离（表示为 d a （ u ， w ））。在本文中，我们介绍了距离保持器的概念。图 G 的子图（分别为Steiner图）G'是 G 的子图（分别为Steiner）D_preserver 如果对于每对顶点 u ， w ∈ V 与 d G （ u ， w ）≥ D ， d G' ，（ u ， w ）= d G （ u ， w ）。我们表明，任何图（resgraph。，digraph）都有一个子图D 保留者，最多具有 O （ n 2 / D ）边缘（分别是圆弧），并且有一些图和有向图，其中任何无向Steiner D -保存器都包含Ω（ n 2 / D ）边缘。但是，我们表明，如果允许使用 D'-I保存的 directed Steiner （或简称为 diS-teiner ）。改善。具体来说，我们表明，对于任何图或有向图，都存在一个带有 O （ n 2 .log D / D .log n 弧，并且该结果严格到一个恒定因子。我们还研究了 D -保存距离标记方案，该标记方案可确保精确计算彼此之间的距离至少为 D 的一对顶点之间的距离。标签大小为 O （ n / D log 2 n ），并且任何 D都需要大小为Ω（ n / D log D ）的标签最后，我们研究了可加扳手。无向图 G =（ V 如果对于任何一对顶点 u ， w ∈ V ， d G' ，（ u ， w ）≤ d G （ u ， w ）+β。对于任何 n -顶点图，存在具有 O （ n 3/2 ）边的加法2跨度，以及具有 O （ n 4/3 ）边缘的Steiner 4扳手。但是，没有构造具有 o （ n 3/2 ）边缘的加力扳手，也没有构造具有 o 的Steiner加力扳手。到目前为止，（ n 4/3 ）条边是已知的。我们设计了加法 O （2 1 /Δ n （1-Δ） [1 /Δ ]-2 / [1/1/1 /]-1）跨度为 O （ n 1 +Δ）的任意图和任何Δ<0。
展开▼
