| Talk: |
|
| Abstract: |
In the constant search for simple and efficient routing algorithms,a particularly attractive approach is greedy routing: every nodeis assigned a coordinate, and routing consists of simply forwarding tothe neighbor closest to the destination.  Unfortunately, in our(Euclidean) world, this strategy is prone to failure.  In this talkI will describe how a small change — working in Hyperbolic space insteadof Euclidean space — allows one to guarantee that greedy routing is alwayssuccessful.I will review the properties of hyperbolic space for this problem, andthen describe how to use it for provably successful greedy routing on a staticgraphs.Next I will describe how to extend this approach to growing graphs.Finally,I will discuss strategies to make this sort of routing efficient — that,toensure that paths through the network are short.This is joint work with Andrej Cvetkovski |
|
