n-Cube Network: Node Disjoint Shortest Paths for Maximal Distance Pairs of Vertices

In parallel and distributed systems many communications take placeconcurrently, so the routing algorithm as well as the underlyinginterconnection network plays a vital role in delivering all themessages efficiently. Fault tolerance and performance are oftenobtained by delivering the messages through node disjoint shortestpaths. In this paper we present two efficient algorithms to construct,under certain conditions, pairwise node disjoint shortest paths forpairs of vertices in an n-cube in the presence of faulty nodes.The first algorithm has O(m^2) time complexity, where mis the input length, and the second one takes O(m^3) but itsolves more general problem instances.