Personal tools
You are here: Home CG seminar Fall 2017 Routing in Unit Disk Graphs
« September 2017 »
September
SuMoTuWeThFrSa
12
3456789
10111213141516
17181920212223
24252627282930
Log in


Forgot your password?
 

Routing in Unit Disk Graphs

Wednesday, November 2nd, 2016, 16:10

Schreiber 309


underline

Routing in Unit Disk Graphs

Paul Seiferth, FU Berlin

Abstract:

Let S be a set of n point-sites in the plane.
The unit disk graph UD(S) on S has vertex set S and an edge
between two distinct sites s,t of S if and only if s and t have
Euclidean distance |st| <= 1.
A routing scheme R for UD(S) assigns to each site s of S a label l(s)
and a routing table rho(s). For any two sites s,t in S, the scheme R
must be able to route a packet from s to t in the
following way: given a current site r (initially, r = s), a header h
(initially empty), and the target
label l(t), the scheme R may consult the current routing table rho(r) to
compute a new site r' and a new header h', where r' is a neighbor of r.
The packet is then routed to r', and the procedure is repeated until the
packet reaches t. The resulting sequence of sites is called the routing
path.
The stretch of R is the maximum ratio of the (Euclidean) length of the
routing path produced by R and the shortest path in UD(S), over all
pairs of distinct sites in S.
For any given eps > 0, we show how to construct a routing scheme for
UD(S) with stretch (1 + eps) using labels of O(log(n)) bits and routing
tables of O(eps^(−5) log^2(n) log^2(D)) bits, where D is the
(Euclidean) diameter of UD(S). The header size is O(log(n)log(D)) bits.
 
Document Actions