Graph Embedding through Random Walk for Shortest Paths Problems. Conference Paper uri icon


  • Abstract. We present a new probabilistic technique of embedding graphs in Zd, the d- dimensional integer lattice, in order to find the shortest paths and shortest distances between pairs of nodes. In our method the nodes of a breath first search (BFS) tree, starting at a particular node, are labeled as the sites found by a branching random walk on Zd. After describing a greedy algorithm for routing (distance estimation) which uses the l1 distance (l2 distance) between the labels of nodes, we approach the following question: Assume that …

publication date

  • October 26, 2009

presented at event