Schloss Dagstuhl - Leibniz-Zentrum für Informatik GmbH Schloss Dagstuhl - Leibniz-Zentrum für Informatik GmbH scholarly article en Ahmed, Reyan; Bodwin, Greg; Sahneh, Faryad Darabi; Hamm, Keaton; Kobourov, Stephen; Spence, Richard https://www.dagstuhl.de/lipics License: Creative Commons Attribution 4.0 license (CC BY 4.0)
when quoting this document, please refer to the following
DOI:
URN: urn:nbn:de:0030-drops-137885
URL:

; ; ; ; ;

Multi-Level Weighted Additive Spanners

pdf-format:


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}
}

Keywords: multi-level, graph spanner, approximation algorithms
Seminar: 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: https://github.com/abureyanahmed/multi_level_weighted_additive_spanners archived at: https://archive.softwareheritage.org/swh:1:dir:95e49892297d01930d1de3c40e2bb2c39ccdd658


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