IEEE Transactions on Computers · 2002 · 51 citations · 15 references
ComputingComputer ScienceAlgorithmsInterconnection NetworksTopologyGraph AlgorithmsGraph TheoryHypercube NetworksNetwork DiameterRoutingRouting AlgorithmsDisjoint Path RoutingDisjoint PathsDisjoint Paths ProblemFolded HypercubeHypercube DiameterHypercube Network DiameterMinimal RoutingNode-disjoint Paths
Routing functions have been shown effective in deriving disjoint paths in the hypercube. In this paper, using a minimal routing function, k+1 disjoint paths from one node to another k+1 distinct nodes are constructed in a k-dimensional folded hypercube whose maximal length is not greater than the diameter plus one, which is minimum in the worst case. For the general case, the maximal length is nearly optimal (/spl les/ the maximal distance between the two end nodes of these k+1 paths plus two). As a by-product, the Rabin number of the folded hypercube is obtained, which is an open problem raised by S.C. Liaw and G.J. Chang (1999).
15
Topological properties of hypercubes
Yousef Saad, Martin H. Schultz · IEEE Transactions on Computers · 1988 · 1.4K citations
Three disjoint path paradigms in star networks
Martin Dietzfelbinger, S. Madhavapeddy, I. Hal Sudborough · 2002 · 88 citations