PM  >> Vol. 7 No. 4 (July 2017)

    Node-Disjoint Shortest and Next-to-Shortest Paths in N-Dimensional Hypercube

  • 全文下载: PDF(508KB) HTML   XML   PP.230-235   DOI: 10.12677/PM.2017.74029  
  • 下载量: 463  浏览量: 962   科研立项经费支持


张云霞:山西省财政税务专科学校,山西 太原

超立方体点不交路径最短路径次短路径Hypercube Node-Disjoint Path Shortest Paths Next-to-Shortest Paths


n维超立方体在并行计算领域有着广泛的应用,其特殊的拓扑结构对大规模的多处理器系统的性能具有重要的影响。本文研究n维超立方体Qn的最短路径问题,采用构造的方法证明了以下结论: Qn中任意两点之间一定存在k条不交的长度为k的最短路径,其中k为此两点之间的Hamming距离。此外,如果放宽最短路径的条件,对两点之间的 Hamming 距离为k的点,长度最多为k+2的不交路径存在至少n条。

N-dimensional hypercube is widely used in the field of parallel computer systems. The special topological structure of n-dimensional hypercube has significantly affected the performance of large multiprocessor systems. In this article, we prove the following result: In n-dimensional hypercube, for any two nodes with hamming distance that equals to k, there are k node-disjoint shortest paths of length k. Additionally, if we include nest-to-shortest paths of length k + 2 in addition to shortest paths, there will be n node-disjoint paths in total.

张云霞. 超立方体中最短和次短的点不交路径[J]. 理论数学, 2017, 7(4): 230-235.


[1] 刘有耀, 杨晓强, 杜慧敏, 等. 一种基于超立方体的可扩展并行计算互连网络拓扑结构[P]. 中国专利, 专利号CN101414952A, 2009-4-22. 5564d7271574b36e509f/CN101414952A.pdf. 763410a55%29&filter=sc_long_sign&tn=SE_xueshus ource_2kduw22v&sc_vurl=http%3A%2F%2Fd.wanfangd
[2] Lai, C.N. (2012) Optimal Construction of All Shortest Node-Disjoint Paths in Hypercubes with Applications. IEEE Transactions on Parallel and Distributed System, 23, 1129-1134.
[3] Lai, C.N. (2015) Constructing All Shortest Node-Disjoint Paths in Torus Networks. Journal of Parallel and Distributed Computing, 75, 123-132.
[4] Chen, X.B. (2013) Paired Many-to-Many Disjoint Path Covers of Hypercubes. Information Sciences, 236, 218-223.
[5] Gu, Q.-P. and Peng, S. (2000) An Efficient Algorithm for the K-Pairwise Disjoint Paths Problem in Hypercubes. Journal of Parallel and Distributed Computing, 60, 764-774.
[6] 陈荷花, 高太平. n维超立方体中点不交的最短路径[J]. 山西大学学报(自然科学版), 2016, 39(2): 229-232.
[7] Chung, I. (2013) Design of a Set of One-to-Many Node-Disjoint and Nearly Shortest Paths on Recursive Circulant Networks. Journal of Korea Multimedia Society, 16, 897-904.
[8] Lai, C.N. (2012) Two Conditions for Reducing the Maximal Length of Node-Disjoint Paths in Hypercubes. Theoretical Computer Science, 418, 82-91.
[9] Wu, R.Y., Chen, G.H., Kuo, Y.L., et al. (2012) Node-Disjoint Paths in Hierarchical Hypercube Networks. Information Sciences, 177, 4200-4207.
[10] Joa, S., Parkb, J.-H. and Chwaa, K.Y. (2013) Paired 2-Disjoint Path Covers and Strongly Hamiltonian Laceability of Bipartite Hypercube-Like Graphs. Information Sciences, 242, 103-112.