Construction algorithms of fault-tolerant paths and disjoint paths in k-ary n-cube networks

作者：Lv, Mengjie; Fan, Jianxi^*; Cheng, Baolei; Yu, Jia; Jia, Xiaojua

来源：Journal of Parallel and Distributed Computing, 2024, 183: 104761.

DOI：10.1016/j.jpdc.2023.104761

• Fault-tolerant paths
• Disjoint paths
• k-ary n-cube networks
• Algorithm
• Performance evaluation

With the increasing demand for information, the number of nodes in the network is increasing rapidly, followed by the problem of information loss and communication delay caused by insufficient communication. Therefore, how to effectively transmit data and minimize communication delay has been a key issue in networks. In this paper, we first propose a fault-tolerant path algorithm of the k-ary n-cube network Qn to obtain a fault-free path between any two distinct fault-free nodes with a faulty node set F subset of V(Qn) and |F| <= 2n - 1. Then, we design two algorithms to construct disjoint paths between any two distinct nodes of Qn without any faults according to whether the two nodes are adjacent or not. Extensive evaluations show that the proposed algorithms has great advantages in average running time.

• 单位
  青岛大学; 南京邮电大学; 苏州大学