Abstract
n-Cube Network: Node Disjoint Shortest Paths for Pairs of Vertices
by: Teofilo F. Gonzalez, F. David Serena
Abstract:
In parallel and distributed systems many communications takeplace concurrently, so the routing algorithm as well as the underlyinginterconnection network plays a vital role in delivering all the messagesefficiently. Fault tolerance and performance are often obtained bydelivering the messages through node disjoint shortest paths. In thispaper we present an efficient algorithm for the n-cube pairwisenode disjoint shortest paths problem in the presence of faulty nodes. Thetime complexity of the algorithm is O(m^{2.5}), when the inputlength is m=O(n^2). (An updated version of this document appearsas UCSB CS TR-2002-15).
Keywords:
fault-tolerance, hypercube, n-cube, node disjoint shortest paths, routing.
Date:
July 2001
Document: 2001-12
