4.5 Article

Optimal node-disjoint paths in folded hypercubes

期刊

出版社

ACADEMIC PRESS INC ELSEVIER SCIENCE
DOI: 10.1016/j.jpdc.2020.09.005

关键词

Folded hypercube; Hypercube; Node-disjoint paths; Matching; Optimization

资金

  1. Ministry of Science and Technology, Taiwan, Republic of China [MOST-107-2221-E-922-024]

向作者/读者索取更多资源

The study in this paper focuses on constructing m node-disjoint paths in a folded hypercube to minimize the total length and maximal length, where m <= n+1. By utilizing two specific routing functions, the construction of these paths can be efficiently carried out for odd and even routing, providing strong evidence for the effective applications of routing functions in deriving node-disjoint paths.
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 0(mn(1.5) + m(3)n) and O(mn(2) + n(2) logn+m(3) n) time, respectively, for odd and even rt 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. (C) 2020 Elsevier Inc. All rights reserved.

作者

我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。

评论

主要评分

4.5
评分不足

次要评分

新颖性
-
重要性
-
科学严谨性
-
评价这篇论文

推荐

暂无数据
暂无数据