- Investigates how to navigate graphs efficiently using the spanning tree
*T*of a graph*G* - Navigation is done through knowledge of a nodes neighbors (or
*k*-neighborhood) and*T* - 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
- 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

- If however, an embedding of the spanning tree is used instead of beacons, delivery is guaranteed
- Its possible to encode node labels compactly s.t. node distances can be found simply by comparing labels (of size log^2
*n*)- So minimum spanning tree routing can be done just with these particularly encoded labels and an adjacency list for each node

- In some classes of graphs routing according to the MST will be optimal
- 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
- These two strategies are “simpler and more compact” than the vanilla method, and in some cases the paths created will be shorter

- The results are all for particular classes of graphs which I’m not going to investigate in particular

Advertisements
(function(){var c=function(){var a=document.getElementById("crt-410704247");window.Criteo?(a.parentNode.style.setProperty("display","inline-block","important"),a.style.setProperty("display","block","important"),window.Criteo.DisplayAcceptableAdIfAdblocked({zoneid:388248,containerid:"crt-410704247",collapseContainerIfNotAdblocked:!0,callifnotadblocked:function(){a.style.setProperty("display","none","important");a.style.setProperty("visbility","hidden","important")}})):(a.style.setProperty("display","none","important"),a.style.setProperty("visibility","hidden","important"))};if(window.Criteo)c();else{if(!__ATA.criteo.script){var b=document.createElement("script");b.src="//static.criteo.net/js/ld/publishertag.js";b.onload=function(){for(var a=0;a<__ATA.criteo.cmd.length;a++){var b=__ATA.criteo.cmd[a];"function"===typeof b&&b()}};(document.head||document.getElementsByTagName("head")[0]).appendChild(b);__ATA.criteo.script=b}__ATA.criteo.cmd.push(c)}})();
(function(){var c=function(){var a=document.getElementById("crt-728827741");window.Criteo?(a.parentNode.style.setProperty("display","inline-block","important"),a.style.setProperty("display","block","important"),window.Criteo.DisplayAcceptableAdIfAdblocked({zoneid:837497,containerid:"crt-728827741",collapseContainerIfNotAdblocked:!0,callifnotadblocked:function(){a.style.setProperty("display","none","important");a.style.setProperty("visbility","hidden","important")}})):(a.style.setProperty("display","none","important"),a.style.setProperty("visibility","hidden","important"))};if(window.Criteo)c();else{if(!__ATA.criteo.script){var b=document.createElement("script");b.src="//static.criteo.net/js/ld/publishertag.js";b.onload=function(){for(var a=0;a<__ATA.criteo.cmd.length;a++){var b=__ATA.criteo.cmd[a];"function"===typeof b&&b()}};(document.head||document.getElementsByTagName("head")[0]).appendChild(b);__ATA.criteo.script=b}__ATA.criteo.cmd.push(c)}})();