The Set-to-Set Disjoint-Path Problem in Perfect Hierarchical Hypercubes
Antoine Bossard, Keiichi Kaneko · The Computer Journal · 2012
The perfect hierarchical hypercube (HHC) interconnection network has been introduced in the literature recently. An HHC can connect many nodes while retaining a low degree and a small diameter. It is thus a suitable topology for interconnection networks of massively parallel systems. We describe in this paper an algorithm solving the set-to-set disjoint-path routing problem in perfect HHCs. In an HHC2m+m, given two sets of m+1 nodes S and D, the proposed algorithm can find m+1 node-disjoint paths between the nodes of S and the nodes of D of lengths at most (m+1) (2m + m + 4) + 3 in O(m2 22m) time complexity.