Node-to-Set Disjoint Paths Problem in Perfect Hierarchical Hypercubes

A. Bossard, K. Kaneko, and S. Peng (Japan)


cube-connected cubes, polynomial algorithm, parallel processing, fault tolerance, interconnection network


A perfect hierarchical hypercube was proposed as a topology for interconnection networks of massively parallel systems, and it has a merit that it can connect many nodes with a small diameter and a small degree. In this paper, we propose an algorithm that solves the node-to-set disjoint paths problem in a hierarchical hypercube network. We show that in HHC2m+m, for any source node s and any set of n ≤ m + 1 destination nodes D = {d1, . . . , dn}, we can find n disjoint paths from s to di (1 ≤ i ≤ n) of length at most 3 · 2m+ m 3/2 (m + 1) + 2 in O(m2 2m) time.

Important Links:

Go Back