Abstract
Complexity of k-Pairwise Disjoint Shortest Paths in the Hypercube and Grid Networks
by: Teofilo Gonzalez and David Serena
Abstract:
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.
Keywords:
Hypercube, n-cube, grids, node disjoint shortest paths, edge disjoint shortest paths, NP-completeness.
Date:
May 2002
Document: 2002-14
