DROPS

Document

DOI: 10.4230/LIPIcs.ESA.2022.37

Spanner Approximations in Practice

Authors: Markus Chimani and Finn Stutzenstein

Published in: LIPIcs, Volume 244, 30th Annual European Symposium on Algorithms (ESA 2022)

Abstract

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) ≤ α⋅ 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.

Cite as

Markus Chimani and Finn Stutzenstein. Spanner Approximations in Practice. In 30th Annual European Symposium on Algorithms (ESA 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 244, pp. 37:1-37:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{chimani_et_al:LIPIcs.ESA.2022.37,
  author =	{Chimani, Markus and Stutzenstein, Finn},
  title =	{{Spanner Approximations in Practice}},
  booktitle =	{30th Annual European Symposium on Algorithms (ESA 2022)},
  pages =	{37:1--37:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-247-1},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{244},
  editor =	{Chechik, Shiri and Navarro, Gonzalo and Rotenberg, Eva and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2022.37},
  URN =		{urn:nbn:de:0030-drops-169750},
  doi =		{10.4230/LIPIcs.ESA.2022.37},
  annote =	{Keywords: Graph spanners, experimental study, algorithm engineering}
}

Search Results

Documents authored by Stutzenstein, Finn

Spanner Approximations in Practice

Abstract

Cite as

Thanks for your feedback!

Could not send message