License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.SEA.2021.16
URN: urn:nbn:de:0030-drops-137885
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2021/13788/
Ahmed, Reyan ;
Bodwin, Greg ;
Sahneh, Faryad Darabi ;
Hamm, Keaton ;
Kobourov, Stephen ;
Spence, Richard
Multi-Level Weighted Additive Spanners
Abstract
Given a graph G = (V,E), a subgraph H is an additive +β spanner if dist_H(u,v) ≤ dist_G(u,v) + β for all u, v ∈ V. A pairwise spanner is a spanner for which the above inequality is only required to hold for specific pairs P ⊆ V × V given on input; when the pairs have the structure P = S × S for some S ⊆ V, it is called a subsetwise spanner. Additive spanners in unweighted graphs have been studied extensively in the literature, but have only recently been generalized to weighted graphs.
In this paper, we consider a multi-level version of the subsetwise additive spanner in weighted graphs motivated by multi-level network design and visualization, where the vertices in S possess varying level, priority, or quality of service (QoS) requirements. The goal is to compute a nested sequence of spanners with the minimum total number of edges. We first generalize the +2 subsetwise spanner of [Pettie 2008, Cygan et al., 2013] to the weighted setting. We experimentally measure the performance of this and several existing algorithms by [Ahmed et al., 2020] for weighted additive spanners, both in terms of runtime and sparsity of the output spanner, when applied as a subroutine to multi-level problem.
We provide an experimental evaluation on graphs using several different random graph generators and show that these spanner algorithms typically achieve much better guarantees in terms of sparsity and additive error compared with the theoretical maximum. By analyzing our experimental results, we additionally developed a new technique of changing a certain initialization parameter which provides better spanners in practice at the expense of a small increase in running time.
BibTeX - Entry
@InProceedings{ahmed_et_al:LIPIcs.SEA.2021.16,
author = {Ahmed, Reyan and Bodwin, Greg and Sahneh, Faryad Darabi and Hamm, Keaton and Kobourov, Stephen and Spence, Richard},
title = {{Multi-Level Weighted Additive Spanners}},
booktitle = {19th International Symposium on Experimental Algorithms (SEA 2021)},
pages = {16:1--16:23},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-185-6},
ISSN = {1868-8969},
year = {2021},
volume = {190},
editor = {Coudert, David and Natale, Emanuele},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2021/13788},
URN = {urn:nbn:de:0030-drops-137885},
doi = {10.4230/LIPIcs.SEA.2021.16},
annote = {Keywords: multi-level, graph spanner, approximation algorithms}
}
