Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userRouting in Strongly Hyperbolic Unit Disk Graphs
128
0
0.0
(
0
)
Added by
Maximilian Katzmann
Publication date
2021
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
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.
rate research
Read More
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 find a minimum cardinality total dominating set for an input graph. We prove that the TDS problem is NP-hard in unit disk graphs. Next, we propose an 8-factor approximation algorithm for the problem. The running time of the proposed approximation algorithm is $O(n log k)$, where $n$ is the number of vertices of the input graph and $k$ is output size. We also show that TDS problem admits a PTAS in unit disk graphs.
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.
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 graphs is NP-hard, numerous approximation algorithms have been proposed in the literature, including some PTAS. However, since the proposal of a linear-time 5-approximation algorithm in 1995, the lack of efficient algorithms attaining better approximation factors has aroused attention. We introduce a linear-time O(n+m) approximation algorithm that takes the usual adjacency representation of the graph as input and outputs a 44/9-approximation. This approximation factor is also attained by a second algorithm, which takes the geometric representation of the graph as input and runs in O(n log n) time regardless of the number of edges. Additionally, we propose a 43/9-approximation which can be obtained in O(n^2 m) time given only the graphs adjacency representation. It is noteworthy that the dominating sets obtained by our algorithms are also independent sets.
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 on exactly $k$ vertices, (3) a cycle on at least $k$ vertices, (4) a feedback vertex set of size at most $k$, and (5) a set of $k$ pairwise vertex-disjoint cycles. For the first three problems, no subexponential time parameterized algorithms were previously known. For the remaining two problems, our algorithms significantly outperform the previously best known parameterized algorithms that run in time $2^{O(k^{0.75}log{k})} cdot n^{O(1)}$. Our algorithms are based on a new kind of tree decompositions of unit disk graphs where the separators can have size up to $k^{O(1)}$ and there exists a solution that crosses every separator at most $O(sqrt{k})$ times. The running times of our algorithms are optimal up to the $log{k}$ factor in the exponent, assuming the Exponential Time Hypothesis.
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.31 on page 82. The techniques used are very similar. He noted that the idea for dealing with the connected version using a constant number of extra layers in the shifting technique not only appeared Zhang et al.[ZGWD09] but also in his 2005 paper [vL05]. Finally, van Leeuwen also informed us that the open problem that we posted has been resolved by Marx~[Mar06, Mar07] who showed that an efficient PTAS for MDS does not exist [Mar06] and under ETH, the running time of $n^{O(1/epsilon)}$ is best possible [Mar07]. We thank Erik Jan van Leeuwen for the information and we regret that we made this mistake. Abstract before retraction: We present two (exponentially) faster PTASs for dominating set problems in unit disk graphs. Given a geometric representation of a unit disk graph, our PTASs that find $(1+epsilon)$-approximate solutions to the Minimum Dominating Set (MDS) and the Minimum Connected Dominating Set (MCDS) of the input graph run in time $n^{O(1/epsilon)}$. This can be compared to the best known $n^{O(1/epsilon log {1/epsilon})}$-time PTAS by Nieberg and Hurink~[WAOA05] for MDS that only uses graph structures and an $n^{O(1/epsilon^2)}$-time PTAS for MCDS by Zhang, Gao, Wu, and Du~[J Glob Optim09]. Our key ingredients are improved dynamic programming algorithms that depend exponentially on more essential 1-dimensional widths of the problems.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
