关于图扩展器的新稀疏性结果

令 G=(V, E) 为一个具有正边权的 n-顶点连通图。如果子图 G′=(V, E′) 中，任意 u, v∈V，在 G′ 中的加权距离至多为 G 中 u 和 v 的加权距离的 t 倍，则称 G′ 为 G 的 t-扩展器。我们考虑构造稀疏扩展器的问题。扩展器的稀疏性由两个标准来衡量：大小，定义为扩展器中的边数，以及权重，定义为扩展器中边权的总和。在本文中，我们集中于构造小权重的扩展器。对于任意正边权图 G，对于任何 t>1，以及任何 ε>0，我们展示可以在多项式时间内构造权重为公式：见文本的 G 的 t-扩展器。我们还展示可以构造权重为 O(1) · wt(MST) 的 (log 2 n)-扩展器。接着我们考虑由 d 维实数范数空间中的一组点诱导的完全图的扩展器。边 xy 的权重是公式：见文本向量的范数。我们展示，对于这些图，可以在多项式时间内构造总权重为 O(log n) · wt(MST) 的 t-扩展器。