Complexity of k-Pairwise Disjoint Shortest Paths in the Hypercube and Grid Networks

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 basic graph topologies, thegrid and the n-cube wherein it is determined that the k-pairwisenode or edge disjoint shortest paths decision problem is NP-completeor NP-hard for a half-partial permutation routing request. Furtherk-pairwise edge disjoint path decision problem in the doubledn-cube for a 1-1 routing request found to be NP-complete.