Academic Journal
Spanner Approximations in Practice
| العنوان: | Spanner Approximations in Practice |
|---|---|
| المؤلفون: | Chimani, Markus, Stutzenstein, Finn |
| المساهمون: | Markus Chimani and Finn Stutzenstein |
| بيانات النشر: | Schloss Dagstuhl – Leibniz-Zentrum für Informatik |
| سنة النشر: | 2022 |
| المجموعة: | DROPS - Dagstuhl Research Online Publication Server (Schloss Dagstuhl - Leibniz Center for Informatics ) |
| مصطلحات موضوعية: | Graph spanners, experimental study, algorithm engineering |
| الوصف: | 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. |
| نوع الوثيقة: | article in journal/newspaper conference object |
| وصف الملف: | application/pdf |
| اللغة: | English |
| Relation: | Is Part Of LIPIcs, Volume 244, 30th Annual European Symposium on Algorithms (ESA 2022); https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2022.37 |
| DOI: | 10.4230/LIPIcs.ESA.2022.37 |
| الاتاحة: | https://doi.org/10.4230/LIPIcs.ESA.2022.37 https://nbn-resolving.org/urn:nbn:de:0030-drops-169750 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2022.37 |
| Rights: | https://creativecommons.org/licenses/by/4.0/legalcode |
| رقم الانضمام: | edsbas.4B93CAB7 |
| قاعدة البيانات: | BASE |
| DOI: | 10.4230/LIPIcs.ESA.2022.37 |
|---|