ﻻ يوجد ملخص باللغة العربية
Given a set $S$ of $n$ points, a weight function $w$ to associate a non-negative weight to each point in $S$, a positive integer $k ge 1$, and a real number $epsilon > 0$, we devise the following algorithms to compute a $k$-vertex fault-tolerant spanner network $G(S, E)$ for the metric space induced by the weighted points in $S$: (1) When the points in $S$ are located in a simple polygon, we present an algorithm to compute $G$ with multiplicative stretch $sqrt{10}+epsilon$, and the number of edges in $G$ (size of $G$) is $O(k n (lg{n})^2)$. (2) When the points in $S$ are located in the free space of a polygonal domain $cal P$ with $h$ number of obstacles, we present an algorithm to compute $G$ with multiplicative stretch $6+epsilon$ and size $O(sqrt{h} k n(lg{n})^2)$. (3) When the points in $S$ are located on a polyhedral terrain, we devise an algorithm to compute $G$ with multiplicative stretch $6+epsilon$ and size $O(k n (lg{n})^2)$.
Recent work has pinned down the existentially optimal size bounds for vertex fault-tolerant spanners: for any positive integer $k$, every $n$-node graph has a $(2k-1)$-spanner on $O(f^{1-1/k} n^{1+1/k})$ edges resilient to $f$ vertex faults, and ther
Recent work has established that, for every positive integer $k$, every $n$-node graph has a $(2k-1)$-spanner on $O(f^{1-1/k} n^{1+1/k})$ edges that is resilient to $f$ edge or vertex faults. For vertex faults, this bound is tight. However, the case
A $k$-spanner of a graph $G$ is a sparse subgraph that preserves its shortest path distances up to a multiplicative stretch factor of $k$, and a $k$-emulator is similar but not required to be a subgraph of $G$. A classic theorem by Thorup and Zwick [
It was recently shown that a version of the greedy algorithm gives a construction of fault-tolerant spanners that is size-optimal, at least for vertex faults. However, the algorithm to construct this spanner is not polynomial-time, and the best-known
Let $V$ be a finite set of vertices in the plane and $S$ be a finite set of polygonal obstacles, where the vertices of $S$ are in $V$. We show how to construct a plane $2$-spanner of the visibility graph of $V$ with respect to $S$. As this graph can