Depth First:Optimal Path Discovery Between Designated Nodes in Random Ring-Based Graphs

作     者：Li Qi Xu Jiasheng Zhang Haonan Kang Huquan Fu Luoyi Long Fei Wang Xinbing Li Qi;Xu Jiasheng;Zhang Haonan;Kang Huquan;Fu Luoyi;Long Fei;Wang Xinbing

作者机构：Department of Electronic EngineeringShanghai Jiao Tong UniversityShanghai 200240China Department of Computer Science and EngineeringShanghai Jiao Tong UniversityShanghai 200240China State Key Laboratory of Media Convergence Production Technology and SystemsXinhua News AgencyBeijing 100077China 

出 版 物：《China Communications》 (中国通信（英文版）)

年 卷 期：2024年第21卷第9期

页      面：225-241页

核心收录：

学科分类：07[理学] 070104[理学-应用数学] 0701[理学-数学] 

基　　金：supported by NSF China(No.61960206002,62020106005,42050105,62061146002) Shanghai Pilot Program for Basic Research-Shanghai Jiao Tong University 

主　　题：connectivity analysis cost minimization path discover ring-based graph 

摘      要：This paper focuses on optimally determining the existence of connected paths between some given nodes in random ring-based *** as a fundamental underlying structure in network modeling,ring topology appears as commonplace in many realistic *** this,we consider graphs composed of rings,with some possible connected paths between *** prior knowledge of the exact node permutations on rings,the existence of each edge can be unraveled through edge testing at a unit cost in one *** problem examined is that of determining whether the given nodes are connected by a path or separated by a cut,with the minimum expected costs *** the problem into different cases based on different topologies of the ring-based networks,we propose the corresponding policies that aim to quickly seek the paths between nodes.A common feature shared by all those policies is that we stick to going in the same direction during edge searching,with edge testing in each step only involving the test between the source and the node that has been tested *** simple searching rule,interestingly,can be interpreted as a delightful property stemming from the neat structure of ring-based networks,which makes the searching process not rely on any sophisticated *** prove the optimality of the proposed policies by calculating the expected cost incurred and making a comparison with the other class of *** effectiveness of the proposed policies is also verified through extensive simulations,from which we even disclose three extra intriguing findings:i)in a onering network,the cost will grow drastically with the number of designated nodes when the number is small and will grow slightly when that number is large;ii)in ring-based network,Depth First is optimal in detecting the connectivity between designated nodes;iii)the problem of multi-ring networks shares large similarity with that of two-ring networks,and a larger number of ties between ri