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

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

Keywords

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

Abstract

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 HHC_2m+m, for any source node s and any set of n ≤ m + 1 destination nodes D = {d₁, . . . , d_n}, we can find n disjoint paths from s to d_i (1 ≤ i ≤ n) of length at most 3 · 2^m+ m 3/2 (m + 1) + 2 in O(m² 2^m) time.

Important Links:

• DOI: 10.2316/P.2010.676-078
• From Proceeding (676) Parallel and Distributed Computing and Networks - 2010

Go Back