The expected distance sum of random shortest-path in-trees over Hamilton path trajectory on grid graph

摘要

The paper deals with shortest path-based in-trees on a grid graph. There root moves among all vertices. As such root mobility pattern, four Hamilton paths are compared. Suppose that each vertex randomly selects the next hop on the shortest path to root. Then S-type root mobility turns out to provide the minimum expected distance sum, followed by numerical experiments.