...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Journal of Parallel and Distributed Computing >Optimal node-disjoint paths in folded hypercubes
【24h】

Optimal node-disjoint paths in folded hypercubes

机译：折叠超机中的最佳节点不相交路径

获取原文
获取原文并翻译 | 示例
           
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

The constructions of node-disjoint paths have been well applied to the study of connectivity, diameter, parallel routing, reliability, and fault tolerance of an interconnection network. In order to minimize the transmission cost and latency, the total length and maximal length of the node-disjoint paths should be minimized, respectively. The construction of node-disjoint paths with their maximal length minimized (in the worst case) has been studied previously in folded hypercubes. In this paper, we construct m node-disjoint paths from one source node to other m (not necessarily distinct) target nodes, respectively, in an n-dimensional folded hypercube so that both of their total length and maximal length (in the worst case) are minimized, where m≤n+1. In addition, each path is either shortest or nearly shortest. The construction of these node-disjoint paths can be efficiently carried out in O(mn~(1.5) + m~3n) and O(mn~2+ n~2 log n+m~3 n) time, respectively, for odd and even n by taking advantage of two specific routing functions, which provide another strong evidence for the effective applications of routing functions in deriving node-disjoint paths, especially for the variants of hypercubes.
机译：节点不相交路径的结构已经很好地应用于互连网络的连接，直径，并行路由，可靠性和容错的研究。为了最小化传输成本和延迟，应分别最小化节点不相交路径的总长度和最大长度。已经在折叠的超速上研究了以最大长度最小化（在最坏情况下）的节点脱节路径的构造。在本文中，我们将来自一个源节点的M节点不相交的路径分别在n维折叠的超立方体中分别从一个源节点到其他m（不一定是不同的）目标节点，使它们的总长度和最大长度（在最坏的情况下）最小化，其中M≤N+ 1。此外，每个路径最短或近最短。可以在O（MN〜（1.5）+ m〜3n）中有效地执行这些节点不相交路径的构造，分别为奇数，分别为O（Mn〜2 + n〜2 log n + m〜3 n）时间甚至是利用两个特定的路由函数，它提供了另一种强大的证据，以便在推导节点不相交的路径中提供路由功能的有效应用，尤其是针对超速的变体。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号