Abstract
Pairwise Disjoint Shortest Paths in the n-Cube and Related Problems
by: Teofilo F. Gonzalez and David Serena
Abstract:
Complexity issues intrinsic to certain fundamental data dissemination problems in high performance network topologies are discussed. In particular, the p-pairwise node, as well as the edge, disjoint shortest paths problem. An efficient algorithm for the p-pairwise node disjoint shortest paths problem when every source point is at a distance at most two from its target is presented and it is shown that for distance three pairs the problem is NP-complete. The problem remains NP-complete even when near-shortest paths are allowed and it is NP-hard for arbitrary length paths. The p-pairwise edge disjoint shortest paths problem is shown to be solvable in polynomial time when every source point is at a distance at most two from its target and it is shown to be NP-complete for distance three pairs. Computational complexity issues for related problems are also discussed.
Keywords:
Fault tolerance, hypercube, n-cube, node disjoint shortest paths, edge disjoint shortest paths, near shortest paths, NP-completeness.
Date:
May 2006
Document: 2006-04
