T.F. Gonzalez and D. Serena (USA)
Fault-tolerance, hypercube, undirected n cube, node disjoint paths and shortest paths, node disjoint near-shortest paths, k-pairwise routing, NP-completeness.
In parallel and distributed systems many communications take place concurrently, so the routing algorithm as well as the underlying interconnection network plays a vital role in delivering all the messages efficiently. Fault tolerance and performance are often obtained by delivering the mes sages through node disjoint shortest paths. In this paper we present results for the undirected n-cube topology. It is determined that the k-pairwise node disjoint shortest paths decision problem is NP-complete even for a restricted form of a partial permutation routing request – a subset of the 1 1 routing request. We also discuss our results for the node disjoint paths and node disjoint near-shortest paths prob lems.
Important Links:
Go Back
