Metric and Geometric Spanners that are Resilient to Degree-Bounded Edge Faults
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866915466874716160 |
|---|---|
| author | Biniaz, Ahmad De Carufel, Jean-Lou Maheshwari, Anil Smid, Michiel |
| author_facet | Biniaz, Ahmad De Carufel, Jean-Lou Maheshwari, Anil Smid, Michiel |
| contents | Let $H$ be an edge-weighted graph, and let $G$ be a subgraph of $H$. We say that $G$ is an $f$-fault-tolerant $t$-spanner for $H$, if the following is true for any subset $F$ of at most $f$ edges of $G$: For any two vertices $p$ and $q$, the shortest-path distance between $p$ and $q$ in the graph $G \setminus F$ is at most $t$ times the shortest-path distance between $p$ and $q$ in the graph $H \setminus F$.
Recently, Bodwin, Haeupler, and Parter generalized this notion to the case when $F$ can be any set of edges in $G$, as long as the maximum degree of $F$ is at most $f$. They gave constructions for general graphs $H$.
We first consider the case when $H$ is a complete graph whose vertex set is an arbitrary metric space. We show that if this metric space contains a $t$-spanner with $m$ edges, then it also contains a graph $G$ with $O(fm)$ edges, that is resilient to edge faults of maximum degree $f$ and has stretch factor $O(ft)$.
Next, we consider the case when $H$ is a complete graph whose vertex set is a metric space that admits a well-separated pair decomposition. We show that, if the metric space has such a decomposition of size $m$, then it contains a graph with at most $(2f+1)^2 m$ edges, that is resilient to edge faults of maximum degree $f$ and has stretch factor at most $1+\varepsilon$, for any given $\varepsilon > 0$. For example, if the vertex set is a set of $n$ points in $\mathbb{R}^d$ ($d$ being a constant) or a set of $n$ points in a metric space of bounded doubling dimension, then the spanner has $O(f^2 n)$ edges.
Finally, for the case when $H$ is a complete graph on $n$ points in $\mathbb{R}^d$, we show how natural variants of the Yao- and $Θ$-graphs lead to graphs with $O(fn)$ edges, that are resilient to edge faults of maximum degree $f$ and have stretch factor at most $1+\varepsilon$, for any given $\varepsilon > 0$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2405_18134 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Metric and Geometric Spanners that are Resilient to Degree-Bounded Edge Faults Biniaz, Ahmad De Carufel, Jean-Lou Maheshwari, Anil Smid, Michiel Computational Geometry Let $H$ be an edge-weighted graph, and let $G$ be a subgraph of $H$. We say that $G$ is an $f$-fault-tolerant $t$-spanner for $H$, if the following is true for any subset $F$ of at most $f$ edges of $G$: For any two vertices $p$ and $q$, the shortest-path distance between $p$ and $q$ in the graph $G \setminus F$ is at most $t$ times the shortest-path distance between $p$ and $q$ in the graph $H \setminus F$. Recently, Bodwin, Haeupler, and Parter generalized this notion to the case when $F$ can be any set of edges in $G$, as long as the maximum degree of $F$ is at most $f$. They gave constructions for general graphs $H$. We first consider the case when $H$ is a complete graph whose vertex set is an arbitrary metric space. We show that if this metric space contains a $t$-spanner with $m$ edges, then it also contains a graph $G$ with $O(fm)$ edges, that is resilient to edge faults of maximum degree $f$ and has stretch factor $O(ft)$. Next, we consider the case when $H$ is a complete graph whose vertex set is a metric space that admits a well-separated pair decomposition. We show that, if the metric space has such a decomposition of size $m$, then it contains a graph with at most $(2f+1)^2 m$ edges, that is resilient to edge faults of maximum degree $f$ and has stretch factor at most $1+\varepsilon$, for any given $\varepsilon > 0$. For example, if the vertex set is a set of $n$ points in $\mathbb{R}^d$ ($d$ being a constant) or a set of $n$ points in a metric space of bounded doubling dimension, then the spanner has $O(f^2 n)$ edges. Finally, for the case when $H$ is a complete graph on $n$ points in $\mathbb{R}^d$, we show how natural variants of the Yao- and $Θ$-graphs lead to graphs with $O(fn)$ edges, that are resilient to edge faults of maximum degree $f$ and have stretch factor at most $1+\varepsilon$, for any given $\varepsilon > 0$. |
| title | Metric and Geometric Spanners that are Resilient to Degree-Bounded Edge Faults |
| topic | Computational Geometry |
| url | https://arxiv.org/abs/2405.18134 |