Node-to-Node Disjoint Paths Problem in Möbius Cubes
David Kocik, Keiichi Kaneko · IEICE Transactions on Information and Systems · 2017
The Möbius cube is a variant of the hypercube. Its advantage is that it can connect the same number of nodes as a hypercube but with almost half the diameter of the hypercube. We propose an algorithm to solve the node-to-node disjoint paths problem in n-Möbius cubes in polynomial-order time of n. We provide a proof of correctness of the algorithm and estimate that the time complexity is O(n2) and the maximum path length is 3n-5.