A multiplicative $\alpha$-spanner $H$ is a subgraph of $G=(V,E)$ with the same vertices and fewer edges that preserves distances up to the factor $\alpha$, i.e., $d_H(u,v)\leq\alpha\cdot d_G(u,v)$ for all vertices $u$, $v$. While many algorithms have been developed to find good spanners in terms of approximation guarantees, no experimental studies comparing different approaches exist. We implemented a rich selection of those algorithms and evaluate them on a variety of instances regarding, e.g., their running time, sparseness, lightness, and effective stretch.
翻译：倍复制的 $ alpha$-spanner $H 是一个由 $G = (V,E) 组成的子集,具有相同的脊椎和较少的边缘,保持与 $\ alpha$ 的距离,即,$d_ H(u,v)\leq\ alpha\cdot d_ G(u,v)$ 。虽然已经开发了许多算法,以寻找在近似保障方面良好的射线员,但是没有比较不同方法的实验性研究。我们实施了丰富的这些算法选择,并评估了有关运行时间、分散性、亮度和有效伸展的多种实例,例如,如运行时间、分散性、亮度和有效伸展。
相关内容
微信扫码咨询专知VIP会员