Can I read Graph Spanners for Group Steiner Distances on EtoBox?

Graph Spanners for Group Steiner Distances by Bilò, Davide; Gualà, Luciano; Leucci, Stefano; Straziota, Alessandro is a scholarly article available to read on EtoBox.

What is Graph Spanners for Group Steiner Distances about?

A spanner is a sparse subgraph of a given graph $G$ which preserves distances, measured w.r.t.\ some distance metric, up to a multiplicative stretch factor. This paper addresses the problem of constructing graph spanners w.r.t.\ the group Steiner metric, which generalizes the recently introduced beer distance metric. In such a metric we are given a collection of groups of required vertices, and we measure the distance between two vertices as the length of the shortest path between them that traverses at least one required vertex from each group. We discuss the relation between group Steiner spanners and classic spanners and we show that they exhibit strong ties with sourcewise spanners w.r.t.\ the shortest path metric. Nevertheless, group Steiner spanners capture several interesting scenarios that are not encompassed by existing spanners. This happens, e.g., for the singleton case, in which each group consists of a single required vertex, thus modeling the setting in which routes need to traverse certain points of interests (in any order). We provide several constructions of group Steiner spanners for both the all-pairs and single-source case, which exhibit various size-stretch tra

Author

Bilò, Davide; Gualà, Luciano; Leucci, Stefano; Straziota, Alessandro

Published

2024

Language

EN