The Expected Distance of Shortest Path-Based In-Trees along Spanning Root Mobility on Grid Graph

Yoshihiro KANEKO  

IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E103-A   No.9   pp.1071-1077
Publication Date: 2020/09/01
Online ISSN: 1745-1337
DOI: 10.1587/transfun.2019KEP0003
Type of Manuscript: Special Section PAPER (Special Section on Circuits and Systems)
grid graph,  the shortest path,  in-tree,  distance,  Hamilton path,  Hamilton cycle,  

Full Text: PDF(842.1KB)>>
Buy this Article

The paper deals with the shortest path-based in-trees on a grid graph. There a root is supposed to move among all vertices. As such a spanning mobility pattern, root trajectories based on a Hamilton path or cycle are discussed. Along such a trajectory, each vertex randomly selects the next hop on the shortest path to the root. Under those assumptions, this paper shows that a root trajectory termed an S-path provides the minimum expected symmetric difference. Numerical experiments show that another trajectory termed a Right-cycle also provides the minimum result.