ﻻ يوجد ملخص باللغة العربية
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 a unit ball graph $G$ with $n$ vertices and a positive constant $epsilon < 1$ finds a $(1+epsilon)$-spanner with constant bounds on its maximum degree and its lightness using only 2-hop neighborhood information. This immediately improves the algorithm of Damian, Pandit, and Pemmaraju which runs in $mathcal{O}(log^*n)$ rounds but has a $mathcal{O}(log Delta)$ bound on its lightness, where $Delta$ is the ratio of the length of the longest edge in $G$ to the length of the shortest edge. We further study the problem in the two dimensional Euclidean plane and we provide a construction with similar properties that has a constant average number of edge intersection per node. This is the first distributed low-intersection topology control algorithm to the best of our knowledge. Our distributed algorithms rely on the maximal independent set algorithm of Schneider and Wattenhofer that runs in $mathcal{O}(log^*n)$ rounds of communication. If a maximal independent set is known beforehand, our algorithms run in constant number of rounds.
Given a set P of n points in the plane, a unit-disk graph G_{r}(P) with respect to a radius r is an undirected graph whose vertex set is P such that an edge connects two points p, q in P if the Euclidean distance between p and q is at most r. The len
Let $Vsubsetmathbb{R}^2$ be a set of $n$ sites in the plane. The unit disk graph $DG(V)$ of $V$ is the graph with vertex set $V$ in which two sites $v$ and $w$ are adjacent if and only if their Euclidean distance is at most $1$. We develop a compact
Let $P subset mathbb{R}^2$ be a planar $n$-point set such that each point $p in P$ has an associated radius $r_p > 0$. The transmission graph $G$ for $P$ is the directed graph with vertex set $P$ such that for any $p, q in P$, there is an edge from $
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
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