A New Node-to-Set Disjoint-Path Algorithm in Perfect Hierarchical Hypercubes

The perfect hierarchical hypercube (HHC) interconnection network, also known as the cube-connected cube, was introduced as a topology for large parallel computers. One of its interesting properties is that it can connect many nodes while retaining a small diameter and a low degree. The first node-to-set disjoint-path routing algorithm in perfect HHCs was previously introduced by Bossard et al. [(2011) Node-to-Set Disjoint-Path Routing in Perfect Hierarchical Hypercubes. Proc. 11th Int. Conf. Computational Science, Tsukuba, Japan, June 1-3. Elsevier, Amsterdam]. In this paper, we propose a novel solution to the node-to-set disjoint-path routing problem in HHC. Inside a (2(m) + m)-dimensional HHC, we shall describe an algorithm that can find disjoint paths between a source node and at most m + 1 destination nodes of maximum length O(2(m)), significantly shorter than the maximum path length O(m2(m)) of Bossard et al. [(2011) Node-to-Set Disjoint-Path Routing in Perfect Hierarchical Hypercubes. Proc. 11th Int. Conf. Computational Science, Tsukuba, Singapore, June 1-3. Elsevier, Amsterdam].