Node-to-node Disjoint Paths in Twisted Crossed Cubes
Hiroki Nagashima, Kousuke Mouri, Keiichi Kaneko · 2018
The twisted crossed cube is a variant of the hypercube. It is promising as a topology of interconnection networks for massively parallel systems. In this paper, we propose an algorithm that constructs n disjoint paths between an arbitrary pair of nodes in an n-dimensional twisted crossed cube. We also prove that the algorithm is correct, its time complexity is O(n2), and the lengths of the paths constructed are at most 4n --- 8. In addition, we conducted a computer experiment to evaluate our algorithm. Experimental results showed that the maximum path lengths are at most 3n + 1.