Set-to-set disjoint paths in a folded hypercube
Set-to-set disjoint paths in a folded hypercube
复制标题
DOI：
10.1016/j.tcs.2024.114562
复制
发表时间：
2024-04-18
影响因子：
1.1
通讯作者：
Kaneko，Keiichi
中科院分区：
文献类型：
--
作者：
Ichida，Hiroyuki;Kaneko，Keiichi
超立方体是一种非常流行的并行系统互连网络拓扑结构，折叠超立方体是超立方体的一种变体。折叠超立方体通过在每个处理单元上引入一个额外的链接来获得更高的性能。因此，有很多关于折叠超立方体的研究活动。本文主要研究了折叠超立方体的拓扑结构，并给出了一个在多项式时间内解决该拓扑结构中的集到集不相交路径问题的算法。我们证明了算法的正确性。证明了该算法的时间复杂度为O（ν 3 log ν），最大路径长度为2 ν+ 2.
The hypercube is a very popular topology for the interconnection networks of parallel systems, and the folded hypercube is a variant of the hypercube. The folded hypercube attains much higher performance by introducing one additional link to each processing element. Therefore, there are many research activities regarding the folded hypercube. We focus on this topology and address an unresolved problem, that is, the set-to-set disjoint paths problem in it. In this paper, we show an algorithm that solves the problem in a folded hypercube in polynomial time. We prove the correctness of the algorithm. Moreover, we show that the time complexity of the algorithm is O (ν 3 log ν) and the maximum length of the paths is 2 ν+ 2 if the algorithm is applied to a ν-dimensional folded hypercube.