ﻻ يوجد ملخص باللغة العربية
For any constants $dge 1$, $epsilon >0$, $t>1$, and any $n$-point set $Psubsetmathbb{R}^d$, we show that there is a geometric graph $G=(P,E)$ having $O(nlog^2 nloglog n)$ edges with the following property: For any $Fsubseteq P$, there exists $F^+supseteq F$, $|F^+| le (1+epsilon)|F|$ such that, for any pair $p,qin Psetminus F^+$, the graph $G-F$ contains a path from $p$ to $q$ whose (Euclidean) length is at most $t$ times the Euclidean distance between $p$ and $q$. In the terminology of robust spanners (Bose et al, SICOMP, 42(4):1720--1736, 2013) the graph $G$ is a $(1+epsilon)k$-robust $t$-spanner of $P$. This construction is sparser than the recent constructions of Buchin, Ol`ah, and Har-Peled (arXiv:1811.06898) who prove the existence of $(1+epsilon)k$-robust $t$-spanners with $nlog^{O(d)} n$ edges.
Efficient algorithms are presented for constructing spanners in geometric intersection graphs. For a unit ball graph in R^k, a (1+epsilon)-spanner is obtained using efficient partitioning of the space into hypercubes and solving bichromatic closest p
Resolving an open question from 2006, we prove the existence of light-weight bounded-degree spanners for unit ball graphs in the metrics of bounded doubling dimension, and we design a simple $mathcal{O}(log^*n)$-round distributed algorithm that given
Seminal works on light spanners over the years provide spanners with optimal or near-optimal lightness in various graph classes, such as in general graphs, Euclidean spanners, and minor-free graphs. Two shortcomings of all previous work on light span
In this thesis, we study two different graph problems. The first problem revolves around geometric spanners. Here, we have a set of points in the plane and we want to connect them with straight line segments, such that there is a path between each
In this paper, we study the online Euclidean spanners problem for points in $mathbb{R}^d$. Suppose we are given a sequence of $n$ points $(s_1,s_2,ldots, s_n)$ in $mathbb{R}^d$, where point $s_i$ is presented in step~$i$ for $i=1,ldots, n$. The objec