Advertisement
Published in:
2014 | OriginalPaper | Chapter
Close to Linear Space Routing Schemes
Authors : Liam Roditty, Roei Tov
Published in: Distributed Computing
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
Let
G
= (
V
,
E
) be an unweighted undirected graph with
n
-vertices and
m
-edges, and let
k
> 2 be an integer. We present a routing scheme with a poly-logarithmic header size, that given a source
s
and a destination
t
at distance Δ from
s
, routes a message from
s
to
t
on a path whose length is
O
(
k
Δ +
m
1/
k
). The total space used by our routing scheme is
$\tilde{O}(mn^{O(1/\sqrt{\log n})})$
, which is almost linear in the number of edges of the graph. We present also a routing scheme with
$\tilde{O}(n^{O(1/\sqrt{\log n})})$
header size, and the same stretch (up to constant factors). In this routing scheme, the routing table of
every
v
∈
V
is at most
$\tilde{O}(kn^{O(1/\sqrt{\log n})}deg(v))$
, where
deg
(
v
) is the degree of
v
in
G
. Our results are obtained by combining a general technique of Bernstein [6], that was presented in the context of dynamic graph algorithms, with several new ideas and observations.