[Nrg-l] NRG Presentation: March/2/2009

Jorge Londono jmlon at cs.bu.edu
Thu Feb 26 10:46:35 EST 2009

Speaker: Andrej Cvetkovski

Title: Hyperbolic Embedding and Routing for Dynamic Graphs

We propose an embedding and routing scheme for arbitrary network 
connectivity graphs, based on greedy routing and utilizing virtual node 
coordinates. In dynamic multihop packet-switching communication 
networks, routing elements can join or leave during network operation or 
exhibit intermittent failures. We present an algorithm for online greedy 
graph embedding in the hyperbolic plane that enables incremental 
embedding of network nodes as they join the network, without disturbing 
the global embedding. Even a single link or node removal may invalidate 
the greedy routing success guarantees in network embeddings based on an 
embedded spanning tree sub- graph. As an alternative to frequent 
reembedding of temporally dynamic network graphs in order to retain the 
greedy embedding property, we propose a simple but robust generalization 
of greedy distance routing called Gravity–Pressure (GP) routing. Our 
routing method always succeeds in finding a route to the destination 
provided that a path exists, even if a significant fraction of links or 
nodes is removed subsequent to the embedding. GP routing does not 
require precomputation or maintenance of special spanning subgraphs and, 
as demonstrated by our numerical evaluation, is particularly suitable 
for operation in tandem with our proposed algorithm for online graph 

Time and place:
4:00pm - Grad Lounge

See you there,


More information about the Nrg-l mailing list