An Algorithm for Node-to-Node Disjoint Paths Problem in a Mobius Cube

摘要

In this paper, we propose an algorithm that solves the node-to-node disjoint paths problem in n-mobius cubes in polynomial-order time of n. We also give a proof of its correctness as well as the estimates of time complexity O(n~3) and the maximum path length O(n~2). We conducted a computer experiment for n = 4 to 31 to measure the average performance of our algorithm. The results show that the average time complexity is O(n~(1.5)) and the maximum path lengths on average are linear to n.