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
Go to the corresponding LIPIcs Volume Portal

Ahmed, Reyan ; Bodwin, Greg ; Sahneh, Faryad Darabi ; Hamm, Keaton ; Kobourov, Stephen ; Spence, Richard

Multi-Level Weighted Additive Spanners

LIPIcs-SEA-2021-16.pdf (2 MB)


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

  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 =		{},
  URN =		{urn:nbn:de:0030-drops-137885},
  doi =		{10.4230/LIPIcs.SEA.2021.16},
  annote =	{Keywords: multi-level, graph spanner, approximation algorithms}

Keywords: multi-level, graph spanner, approximation algorithms
Collection: 19th International Symposium on Experimental Algorithms (SEA 2021)
Issue Date: 2021
Date of publication: 31.05.2021
Supplementary Material: All algorithms, implementations, the ILP solver, experimental data and analysis are available on Github:
Software: archived at:

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI