HOT-POTATO ALGORITHMS FOR PERMUTATION ROUTING

被引：20

作者：

NEWMAN, I ^{[1
]}

SCHUSTER, A ^{[1
]}

机构：

[1] TECHNION ISRAEL INST TECHNOL,DEPT COMP SCI,IL-32000 HAIFA,ISRAEL

来源：

IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS | 1995年 / 6卷 / 11期

关键词：

DEFLECTION ROUTING; PACKET ROUTING; PARALLEL ALGORITHMS;

D O I：

10.1109/71.476188

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

We develop a methodology for the design of hot-potato algorithms for routing permutations. The basic idea is to convert existing store-and-forward routing algorithms to hot-potato algorithms, Using it, we obtain the following complexity bounds for permutation routing: n x n Mesh: 7n + o(n) steps. 2'' hypercube: O(n(2)) steps. n x n Torus: 4n + o(n) steps. The algorithm for the two-dimensional grid is the first to be both deterministic and asymptotically optimal, The algorithm for the 2''-nodes Boolean cube is the first deterministic algorithm that achieves a complexity of o(2'') steps.

引用

页码：1168 / 1176

页数：9