1 Search Results for "Stutzenstein, Finn"

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-dev.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}
}
  • Refine by Author
  • 1 Chimani, Markus
  • 1 Stutzenstein, Finn

  • Refine by Classification
  • 1 General and reference → Experimentation
  • 1 Theory of computation → Sparsification and spanners

  • Refine by Keyword
  • 1 Graph spanners
  • 1 algorithm engineering
  • 1 experimental study

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2022

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact