Journal of Graph Algorithms and Applications
Journal of Graph Algorithms and Applications
复制标题
DOI：
--
复制
发表时间：
--
期刊：
影响因子：
--
通讯作者：
Y. Kambayashi;Eiji Miyano
中科院分区：
文献类型：
--
作者：
Y. Kambayashi;Eiji Miyano
我们在网格网络上给出了两个新的上限，以进行遗漏的置换路由：让N为每个网格中的总量。带有恒定的队列的网格。 n二维，N 1/3×N 1/3×N 1/3粒子，该算法最多可以在每个数据包的路径中进行三个弯曲。即，最多两个，然后绑定跳到ω（n 2/3），如ESA'97中所示。
We give two, new upper bounds for oblivious permutation routing on the mesh networks: Let N be the total number of processors in each mesh. One is an O(N 0.75) algorithm on the two-dimensional, √ N × √ N mesh with constant queue-size. This is the first algorithm which improves substantially the trivial O(N) bound for oblivious routing in the mesh networks with constant queue-size. The other is a 1.16 √ N + o(√ N) algorithm on the three-dimensional, N 1/3 × N 1/3 × N 1/3 mesh with unlimited queue-size. This algorithm allows at most three bends in the path of each packet. If the number of bends is restricted to minimal, i.e., at most two, then the bound jumps to Ω(N 2/3) as was shown in ESA'97.