ﻻ يوجد ملخص باللغة العربية
Greedy routing has been studied successfully on Euclidean unit disk graphs, which we interpret as a special case of hyperbolic unit disk graphs. While sparse Euclidean unit disk graphs exhibit grid-like structure, we introduce strongly hyperbolic unit disk graphs as the natural counterpart containing graphs that have hierarchical network structures. We develop and analyze a routing scheme that utilizes these hierarchies. On arbitrary graphs this scheme guarantees a worst case stretch of $max{3, 1+2b/a}$ for $a > 0$ and $b > 1$. Moreover, it stores $mathcal{O}(k(log^2{n} + log{k}))$ bits at each vertex and takes $mathcal{O}(k)$ time for a routing decision, where $k = pi e (1 + a)/(2(b - 1)) (b^2 text{diam}(G) - 1) R + log_b(text{diam}(G)) + 1$, on strongly hyperbolic unit disk graphs with threshold radius $R > 0$. In particular, for hyperbolic random graphs, which have previously been used to model hierarchical networks like the internet, $k = mathcal{O}(log^2{n})$ holds asymptotically almost surely. Thus, we obtain a worst-case stretch of $3$, $mathcal{O}(log^4 n)$ bits of storage per vertex, and $mathcal{O}(log^2 n)$ time per routing decision on such networks. This beats existing worst-case lower bounds. Our proof of concept implementation indicates that the obtained results translate well to real-world networks.
Let $G=(V,E)$ be an undirected graph. We call $D_t subseteq V$ as a total dominating set (TDS) of $G$ if each vertex $v in V$ has a dominator in $D$ other than itself. Here we consider the TDS problem in unit disk graphs, where the objective is to fi
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
A unit disk graph is the intersection graph of n congruent disks in the plane. Dominating sets in unit disk graphs are widely studied due to their application in wireless ad-hoc networks. Because the minimum dominating set problem for unit disk graph
We give algorithms with running time $2^{O({sqrt{k}log{k}})} cdot n^{O(1)}$ for the following problems. Given an $n$-vertex unit disk graph $G$ and an integer $k$, decide whether $G$ contains (1) a path on exactly/at least $k$ vertices, (2) a cycle o
Retraction note: After posting the manuscript on arXiv, we were informed by Erik Jan van Leeuwen that both results were known and they appeared in his thesis[vL09]. A PTAS for MDS is at Theorem 6.3.21 on page 79 and A PTAS for MCDS is at Theorem 6.3.