The Expected Distance of Shortest Path-Based In-Trees along Spanning Root Mobility on Grid Graph
Summary :
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.
- Publication
- IEICE TRANSACTIONS on Fundamentals Vol.E103-A No.9 pp.1071-1077
- Publication Date
- 2020/09/01
- Publicized
- Online ISSN
- 1745-1337
- DOI
- 10.1587/transfun.2019KEP0003
- Type of Manuscript
- Special Section PAPER (Special Section on Circuits and Systems)
- Category
Authors
Yoshihiro KANEKO
Gifu University
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
Copy
Yoshihiro KANEKO, "The Expected Distance of Shortest Path-Based In-Trees along Spanning Root Mobility on Grid Graph" in IEICE TRANSACTIONS on Fundamentals,
vol. E103-A, no. 9, pp. 1071-1077, September 2020, doi: 10.1587/transfun.2019KEP0003.
Abstract: 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.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/transfun.2019KEP0003/_p
Copy
@ARTICLE{e103-a_9_1071,
author={Yoshihiro KANEKO, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={The Expected Distance of Shortest Path-Based In-Trees along Spanning Root Mobility on Grid Graph},
year={2020},
volume={E103-A},
number={9},
pages={1071-1077},
abstract={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.},
keywords={},
doi={10.1587/transfun.2019KEP0003},
ISSN={1745-1337},
month={September},}
Copy
TY - JOUR
TI - The Expected Distance of Shortest Path-Based In-Trees along Spanning Root Mobility on Grid Graph
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 1071
EP - 1077
AU - Yoshihiro KANEKO
PY - 2020
DO - 10.1587/transfun.2019KEP0003
JO - IEICE TRANSACTIONS on Fundamentals
SN - 1745-1337
VL - E103-A
IS - 9
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - September 2020
AB - 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.
ER -
English
