How to Use Spanning Trees to Navigate in Graphs. Dragan, Xiang. FOCS 2009.


  1. Investigates how to navigate graphs efficiently using the spanning tree T of a graph G
  2. Navigation is done through knowledge of a nodes neighbors (or k-neighborhood) and T
  3. In wireless networks, a common heuristic is to simply move packets to the neighbor that is geographically closest to the destination.  Of course this scheme can run into problems so there are various methods to try and escape local optima
    1. If geographic distances arent applicable or unkown, other similar methods measure location based on proximity to a number of “beacon” nodes.  This usually works well in practice, but does not have theoretic guarantees
  4. If however, an embedding of the spanning tree is used instead of beacons, delivery is guaranteed
  5. Its possible to encode node labels compactly s.t. node distances can be found simply by comparing labels (of size log^2 n)
    1. So minimum spanning tree routing can be done just with these particularly encoded labels and an adjacency list for each node
  6. In some classes of graphs routing according to the MST will be optimal
  7. There are two additional tree routing strategies (aside from the obvious one) that need a small amount of information for each node (logarithmic) that encodes how far up the spanning tree it is
    1. These two strategies are “simpler and more compact” than the vanilla method, and in some cases the paths created will be shorter
  8. The results are all for particular classes of graphs which I’m not going to investigate in particular
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: