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  
  • 下载量: 510  浏览量: 1,016   科研立项经费支持

作者:  

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

关键词:
超立方体点不交路径最短路径次短路径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. https://doi.org/10.12677/PM.2017.74029

参考文献

[1] 刘有耀, 杨晓强, 杜慧敏, 等. 一种基于超立方体的可扩展并行计算互连网络拓扑结构[P]. 中国专利, 专利号CN101414952A, 2009-4-22. https://docs.google.com/viewer?url=patentimages.storage.googleapis.com/pdfs/ 5564d7271574b36e509f/CN101414952A.pdf. http://xueshu.baidu.com/s?wd=paperuri%3A%281dc376a4b0d242325b1c8fc 763410a55%29&filter=sc_long_sign&tn=SE_xueshus ource_2kduw22v&sc_vurl=http%3A%2F%2Fd.wanfangd ata.com.cn%2FPatent_CN200810232462.0.aspx&ie=utf-8&sc_us=18417171916466020850
[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.
https://doi.org/10.1109/TPDS.2011.261
[3] Lai, C.N. (2015) Constructing All Shortest Node-Disjoint Paths in Torus Networks. Journal of Parallel and Distributed Computing, 75, 123-132.
https://doi.org/10.1016/j.jpdc.2014.09.004
[4] Chen, X.B. (2013) Paired Many-to-Many Disjoint Path Covers of Hypercubes. Information Sciences, 236, 218-223.
https://doi.org/10.1016/j.ipl.2011.10.010
[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. http://www.sciencedirect.com/science/article/pii/S0743731500916320
https://doi.org/10.1006/jpdc.2000.1632
[6] 陈荷花, 高太平. n维超立方体中点不交的最短路径[J]. 山西大学学报(自然科学版), 2016, 39(2): 229-232.
https://doi.org/10.13451/j.cnki.shanxi.univ(nat.sci.).2016.02.011
[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.
https://doi.org/10.9717/kmms.2013.16.7.897
[8] Lai, C.N. (2012) Two Conditions for Reducing the Maximal Length of Node-Disjoint Paths in Hypercubes. Theoretical Computer Science, 418, 82-91.
https://doi.org/10.1016/j.tcs.2011.11.009
[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.
https://doi.org/10.1016/j.ins.2007.02.035
[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.
https://doi.org/10.1016/j.ins.2013.04.013