超立方体中最短和次短的点不交路径
Node-Disjoint Shortest and Next-to-Shortest Paths in N-Dimensional Hypercube
摘要:
n维超立方体在并行计算领域有着广泛的应用，其特殊的拓扑结构对大规模的多处理器系统的性能具有重要的影响。本文研究n维超立方体Qn的最短路径问题，采用构造的方法证明了以下结论： Qn中任意两点之间一定存在k条不交的长度为k的最短路径，其中k为此两点之间的Hamming距离。此外，如果放宽最短路径的条件，对两点之间的 Hamming 距离为k的点，长度最多为k+2的不交路径存在至少n条。
Abstract:
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.
参考文献
|
[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
|