k-Pairwise disjoint shortest paths: Algorithms and complexity

In parallel and distributed systems many communications take place concurrently, so the routing algorithm as well as the underlying interconnection network topology plays a significant 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 thesis we examine the k-pairwise node (edge) disjoint shortest paths problem in both doubled and undirected graph topologies of the grid and the n-cube. Herein it is shown that the k-pairwise node as well as the k-pairwise edge disjoint shortest paths decision problems are NP-complete and remain NP-complete even for many different restrictions on the problem. However, we also present efficient algorithms for other restricted versions of our problems. The most interesting ones are the ones we have developed for the extreme version of the k-pairwise node disjoint shortest paths problem in the n-cube. We also show that the k-pairwise node disjoint paths problem in the n-cube is NP-hard. This result is used to show that the k-pairwise node disjoint near-shortest paths problem, which may be viewed as an approximation of the original problem, is also NP-complete. For the grid topology we have obtained interesting NP-complete and NP-hard results for both the k-pairwise node and edge disjoint shortest paths problems.