n-Cube Network: Time Complexity of Node Disjoint Paths for k-Pairs of Vertices

In parallel and distributed many communications take placeconcurrently, so the interconnection network as well as routing algorithms playa vital role in delivering all the messages efficiently. In this paper we showthat finding k node disjoint shortest paths in an n-cube isNP-complete even when the length of each of the paths is at most three, butpolynomially solvable, even on general graphs, when the length of each path isat most two. The problem of finding node disjoint shortest path problem in amesh when one restricts all paths being of length at most 3 is polynomiallysolvable. (An updated version appears as TR 2002-14).