n-Cube network: node disjoint shortest paths for maximal distance pairs of vertices

摘要

In parallel and distributed systems many communications take place concurrently, so the routing algorithm as well as the underlying interconnection network play a vital role in delivering all the messages efficiently. Fault tolerance and performance are often obtained by delivering the messages through node disjoint shortest paths. In this paper we present two efficient algorithms to construct, under certain conditions, pairwise node disjoint shortest paths for pairs of vertices in an n-cube in the presence of faulty nodes. The first algorithm has O(m~2) time complexity, where m is the number of input bits, and the second one takes O(m~3), but it solves more general problem instances. We also present an efficient algorithm for the extreme version of the edge disjoint shortest paths problem when n is odd.