Let G = (V,E) be an undirected unweighted graph on n vertices. A subgraph H of G is called an (α, β) spanner of G if for each (u, v) ∈ V × V, the u-v distance in H is at most α • δ_G(u, v) + β. The following is a natural relaxation of the above problem: we care for only certain distances, these are captured by the set P is contained in V × V and the problem is to construct a sparse subgraph H, called an (α, β) P-spanner, where for every (u, v) ∈ V, the u-v distance in H is at most α • δ_G(u, v)+β. We show how to construct a (1,2) P-spanner of size O(n · |P|~(1/3)) and a (1,2) (S × V)-spanner of size O(n · (n|S|)~(1/4)). A D-spanner is a P-spanner when P is described implicitly via a distance threshold D as V = {(u,v) : δ(u,v) ≥ D}. For a given D ∈ Z~+, we show how to construct a (1,4) D-spanner of size O(n~(3/2)/D~(1/4)) and for D ≥ 2, a (1,41ogD) D-spanner of size O(n~(3/2)/D~(1/2)).
展开▼
机译：令G =（V，E）是n个顶点上的无向未加权图。如果对于每个（u，v）∈V×V，H中的u-v距离最大为α•δ_G（u，v）+β，则G的子图H称为G的（α，β）扳手。以下是上述问题的自然缓解：我们仅关注某些距离，这些距离被集合P捕获，且包含在V×V中，问题是构造一个稀疏的子图H，称为（α，β）P -spanner，其中对于每个（u，v）∈V，H中的uv距离最大为α•δ_G（u，v）+β。我们展示了如何构造大小为O（n·| P |〜（1/3））的（1,2）P扳手和大小为O（n· （n | S |）〜（1/4））。当通过距离阈值D隐式描述P为V = {（u，v）：δ（u，v）≥D}时，D扳手是P扳手。对于给定的D∈Z〜+，我们展示了如何构造大小为O（n〜（3/2）/ D〜（1/4））的（1,4）D扳手，对于D≥2，a大小为O（n〜（3/2）/ D〜（1/2））的（1.41ogD）D扳手。
展开▼
