For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
The Expected Distance of Shortest Path-Based In-Trees along Spanning Root Mobility on Grid Graph
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 2020/09/01
Online ISSN: 1745-1337
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)>>
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.