Report ID
2001-12
Report Authors
Teofilo F. Gonzalez, F. David Serena
Report Date
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).
Document
2001-12.ps232.23 KB