Concentrations, load balancing, multicasting and partial permutation routing on hypercube parallel computers

Some basic algorithms on hypercube interconnection networks are addressed and then applied to concentration, superconcentration, multicasting, partial permutation routing, and load balancing problems in this paper. The results show that both concentration and superconcentration problems can be solved in O(n) time and the multicasting and partial permutation routing problems in O(n²) time with O(1) buffers for each node, where n is the dimension of hypercube interconnection networks. The load balancing problem based on superconcentration can be solved in O(Mn) time, where M is the maximum number of tasks in each node.