In parallel and distributed systems many communications take place concurrently. The efficient delivery of all the messages depends on the routing algorithms as well as the underlying interconnection network topology. The grid is a planar network topology that lends itself for efficient VLSI implementation and therefore is of interest for theoretical analysis. Frequently, networks and switches achieve high performance by delivering the messages through shortest paths. In addition, network fault tolerance improves through insuring that the traversed paths are both edge and/or node disjoint. The edge disjoint criterion is useful when network links are the predominant constraint, and the node disjoint criterion becomes important when switches are the fault tolerant bottleneck. Because the latter necessarily implies the former, it is apparent that node disjointness contributes to fault tolerance and enhanced performance. In this paper, we examine the k-pairwise node and edge disjoint shortest paths problem in the undirected graph topology of the grid. Herein it is shown that the k-pairwise node as well as the k-pairwise edge disjoint shortest paths decision problems are NP-hard, and remain NP-hard even for many different restrictions on the problem. We also discuss polynomial time algorithms for restricted versions of our problems.
['Teofilo F. Gonzalez', 'David Serena']
Complexity of pairwise shortest path routing in the grid