Pairwise edge disjoint shortest paths in the n-cube

Complexity issues intrinsic to certain fundamental data dissemination problems in high-performance network topologies are discussed. In particular, we study the p-pairwise edge disjoint shortest paths problem. An efficient algorithm for the case when every source point is at a distance at most two from its target is presented and for pairs at a distance at most three we show that the problem is NP-complete.