@article {3067, title = {Pure greedy Hot-Potato routing in the 2-d mesh with random destinations}, journal = {Parallel Processing Letters Vol. 7 No. 3}, year = {1997}, pages = { 249 - 258}, abstract = {We analyze here a pure greedy hot-potato routing strategy on a two-dimensional mesh of n^2 nodes. We specifically study the case of n^ 2 packets, originating one per node, to be delivered at random uniform destinations. Each packet attempts to follow the shortest path leading first to the destination row/column (whichever is closest) and then to the actual destination node. A de ection policy is adopted to solve con icts. We prove that all packets are delivered to the destinations in average time O(nlogn). The average is taken over all possible destination functions. No average case analysis of pure greedy hot-potato routing was known up to now.}, author = {Paul Spirakis and Vasilis Triantafillou} }