Title: Near-Optimal Distributed Routing with Low Memory.

Author: Michael Elkin and Ofer Neiman 

Abstract: Distributed {\em routing} is one of the most central and fundamental problems in the area of Distributed Graph Algorithms. 
It was extensively studied for almost thirty years. Nevertheless, the currently existing solutions for this problem require either prohibitively large construction 
(aka preprocessing) time, or prohibitively large memory usage either during the construction or during the routing phase, and suffer from suboptimal labels and 
tables' sizes.

We devise a distributed routing scheme that enjoys the best of all worlds. Specifically, its construction time and memory requirements during the 
construction phase are near-optimal, and so is also the tradeoff between the sizes of routing tables and labels on the one hand, and the stretch on the other.



On the way to this result, we also improve upon existing solutions for the distributed exact {\em tree} routing problem. Previous solutions require $\Omega(\sqrt{n})$ 
memory, and provide tables and labels of size $O(\log n)$ and $O(\log^2 n)$, respectively.

 Our solution, on the other hand, requires just  $O(\log n)$ memory, and has 
tables of size $O(1)$, and labels of size $O(\log n)$. These bounds match the bounds of the best-known centralized solution.