

























A multiplicative $α$-spanner $H$ is a subgraph of $G=(V,E)$ with the same vertices and fewer edges that preserves distances up to the factor $α$, i.e., $d_H(u,v)\leqα\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.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。