Subsetwise and Multi-Level Additive Spanners with Lightness Guarantees
Fuente:
arXiv
Guardado en:
| Autores principales: | , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2024
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866910829849346048 |
|---|---|
| author | Ahmed, Reyan Mondal, Debajyoti Nishat, Rahnuma Islam |
| author_facet | Ahmed, Reyan Mondal, Debajyoti Nishat, Rahnuma Islam |
| contents | An \emph{additive +$βW$ spanner} of an edge weighted graph $G=(V,E)$ is a subgraph $H$ of $G$ such that for every pair of vertices $u$ and $v$, $d_{H}(u,v) \le d_G(u,v) + βW$, where $d_G(u,v)$ is the shortest path length from $u$ to $v$ in $G$. While additive spanners are very well studied in the literature, spanners that are both additive and lightweight have been introduced more recently [Ahmed et al., WG 2021]. Here the \emph{lightness} is the ratio of the spanner weight to the weight of a minimum spanning tree of $G$. In this paper, we examine the widely known subsetwise setting when the distance conditions need to hold only among the pairs of a given subset $S$. We generalize the concept of lightness to subset-lightness using a Steiner tree and provide polynomial-time algorithms to compute subsetwise additive $+εW$ spanner and $+(4+ε) W$ spanner with $O_ε(|S|)$ and $O_ε(|V_H|^{1/3} |S|^{1/3})$ subset-lightness, respectively, where $ε$ is an arbitrary positive constant. We next examine a multi-level version of spanners that often arises in network visualization and modeling the quality of service requirements in communication networks. The goal here is to compute a nested sequence of spanners with the minimum total edge weight. We provide an $e$-approximation algorithm to compute multi-level spanners assuming that an oracle is given to compute single-level spanners, improving a previously known 4-approximation [Ahmed et al., IWOCA 2023]. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2411_07505 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Subsetwise and Multi-Level Additive Spanners with Lightness Guarantees Ahmed, Reyan Mondal, Debajyoti Nishat, Rahnuma Islam Data Structures and Algorithms An \emph{additive +$βW$ spanner} of an edge weighted graph $G=(V,E)$ is a subgraph $H$ of $G$ such that for every pair of vertices $u$ and $v$, $d_{H}(u,v) \le d_G(u,v) + βW$, where $d_G(u,v)$ is the shortest path length from $u$ to $v$ in $G$. While additive spanners are very well studied in the literature, spanners that are both additive and lightweight have been introduced more recently [Ahmed et al., WG 2021]. Here the \emph{lightness} is the ratio of the spanner weight to the weight of a minimum spanning tree of $G$. In this paper, we examine the widely known subsetwise setting when the distance conditions need to hold only among the pairs of a given subset $S$. We generalize the concept of lightness to subset-lightness using a Steiner tree and provide polynomial-time algorithms to compute subsetwise additive $+εW$ spanner and $+(4+ε) W$ spanner with $O_ε(|S|)$ and $O_ε(|V_H|^{1/3} |S|^{1/3})$ subset-lightness, respectively, where $ε$ is an arbitrary positive constant. We next examine a multi-level version of spanners that often arises in network visualization and modeling the quality of service requirements in communication networks. The goal here is to compute a nested sequence of spanners with the minimum total edge weight. We provide an $e$-approximation algorithm to compute multi-level spanners assuming that an oracle is given to compute single-level spanners, improving a previously known 4-approximation [Ahmed et al., IWOCA 2023]. |
| title | Subsetwise and Multi-Level Additive Spanners with Lightness Guarantees |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2411.07505 |