Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userOptimal Spanners for Unit Ball Graphs in Doubling Metrics
142
0
0.0
(
0
)
Added by
Hadi Khodabandeh
Publication date
2021
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
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.
rate research
Read More
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 length of any path in G_r(P) is the number of edges of the path. Given a value lambda>0 and two points s and t of P, we consider the following reverse shortest path problem: finding the smallest r such that the shortest path length between s and t in G_r(P) is at most lambda. It was known previously that the problem can be solved in O(n^{4/3} log^3 n) time. In this paper, we present an algorithm of O(lfloor lambda rfloor cdot n log n) time and another algorithm of O(n^{5/4} log^2 n) time.
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 routing scheme for $DG(V)$. The routing scheme preprocesses $DG(V)$ by assigning a label $l(v)$ to every site $v$ in $V$. After that, for any two sites $s$ and $t$, the scheme must be able to route a packet from $s$ to $t$ as follows: given the label of a current vertex $r$ (initially, $r=s$) and the label of the target vertex $t$, the scheme determines a neighbor $r$ of $r$. Then, the packet is forwarded to $r$, and the process continues until the packet reaches its desired target $t$. The resulting path between the source $s$ and the target $t$ is called the routing path of $s$ and $t$. The stretch of the routing scheme is the maximum ratio of the total Euclidean length of the routing path and of the shortest path in $DG(V)$, between any two sites $s, t in V$. We show that for any given $varepsilon>0$, we can construct a routing scheme for $DG(V)$ with diameter $D$ that achieves stretch $1+varepsilon$ and label size $O(log Dlog^3n/loglog n)$ (the constant in the $O$-Notation depends on $varepsilon$). In the past, several routing schemes for unit disk graphs have been proposed. Our scheme is the first one to achieve poly-logarithmic label size and arbitrarily small stretch without storing any additional information in the packet.
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 $p$ to $q$ if and only if $d(p, q) leq r_p$. Let $t > 1$ be a constant. A $t$-spanner for $G$ is a subgraph $H subseteq G$ with vertex set $P$ so that for any two vertices $p,q in P$, we have $d_H(p, q) leq t d_G(p, q)$, where $d_H$ and $d_G$ denote the shortest path distance in $H$ and $G$, respectively (with Euclidean edge lengths). We show how to compute a $t$-spanner for $G$ with $O(n)$ edges in $O(n (log n + log Psi))$ time, where $Psi$ is the ratio of the largest and smallest radius of a point in $P$. Using more advanced data structures, we obtain a construction that runs in $O(n log^5 n)$ time, independent of $Psi$. We give two applications for our spanners. First, we show how to use our spanner to find a BFS tree in $G$ from any given start vertex in $O(n log n)$ time (in addition to the time it takes to build the spanner). Second, we show how to use our spanner to extend a reachability oracle to answer geometric reachability queries. In a geometric reachability query we ask whether a vertex $p$ in $G$ can reach a target $q$ which is an arbitrary point in the plane (rather than restricted to be another vertex $q$ of $G$ in a standard reachability query). Our spanner allows the reachability oracle to answer geometric reachability queries with an additive overhead of $O(log nlog Psi)$ to the query time and $O(n log Psi)$ to the space.
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 pair problems. The spanner construction has almost equivalent complexity to the construction of Euclidean minimum spanning trees. The results are extended to arbitrary ball graphs with a sub-quadratic running time. For unit ball graphs, the spanners have a small separator decomposition which can be used to obtain efficient algorithms for approximating proximity problems like diameter and distance queries. The results on compressed quadtrees, geometric graph separators, and diameter approximation might be of independent interest.
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 spanners are: (1) The techniques are ad hoc per graph class, and thus cant be applied broadly (e.g., some require large stretch and are thus suitable to general graphs, while others are naturally suitable to stretch $1 + epsilon$). (2) The runtimes of these constructions are almost always sub-optimal, and usually far from optimal. This work aims at initiating a unified theory of light spanners by presenting a single framework that can be used to construct light spanners in a variety of graph classes. This theory is developed in two papers. The current paper is the first of the two -- it lays the foundations of the theory of light spanners and then applies it to design fast constructions with optimal lightness for several graph classes. Our new constructions are significantly faster than the state-of-the-art for every examined graph class; moreover, our runtimes are near-linear and usually optimal. Specifically, this paper includes the following results: (i) An $O(m alpha(m,n))$-time construction of $(2k-1)(1+epsilon)$-spanner with lightness $O(n^{1/k})$ for general graphs; (ii) An $O(nlog n)$-time construction of Euclidean $(1+epsilon)$-spanners with lightness and degree both bounded by constants in the basic algebraic computation tree (ACT) model. This construction resolves a major problem in the area of geometric spanners, which was open for three decades; (iii) An $O(nlog n)$-time construction of $(1+epsilon)$-spanners with constant lightness and degree, in the ACT model for unit disk graphs; (iv) a linear-time algorithm for constructing $(1+epsilon)$-spanners with constant lightness for minor-free graphs.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
