计算机科学 ›› 2024, Vol. 51 ›› Issue (9): 346-356.doi: 10.11896/jsjkx.230700041
李夏晶1,2, 程宝雷1,2, 樊建席1, 王岩1,2, 李晓瑞1,2
LI Xiajing1,2, CHENG Baolei1,2, FAN Jianxi1, WANG Yan1,2, LI Xiaorui1,2
摘要: 近年来,围绕互连网络的研究工作越来越多。其中独立生成树(Independent Spanning Trees,ISTs)可以应用于信息的可靠传输、并行传输、安全分发以及故障服务器的并行诊断中,因此受到了许多研究者的关注。在一对多广播、可靠通信、多节点广播、容错广播、安全消息分发、IP快速重路由等网络通信中,边独立生成树(Edge-Independent Spanning Trees,EISTs)发挥着重要作用。n维增广立方体AQn是n维超立方体Qn的节点对称变型,它具有超立方体及其变型所没有的一些可嵌入性质。然而,目前增广立方体上边独立生成树的构造方法都是串行构造的。文中首先提出了一种并行算法,用于构造以AQn中的任意节点为根的2n-1棵树。然后证明算法得到的2n-1棵树是高度为n的边独立生成树,算法的时间复杂度为O(N),其中N表示增广立方体中的节点数。最后通过模拟实验来验证了所提方法的准确性。
中图分类号:
[1]SAAD Y,SCHULTZ M H.Topological properties of hypercubes [J].IEEE Transactions on Computers,1988,37(7):867-872. [2]CHOUDUM S A,SUNITHA V.Augmented cubes [J].Networks,2002,40(2):71-84. [3]TSENG Y C,WANG S Y,HO C W.Efficient broadcasting inwormhole-routed multicomputers:A network-partitioning approach [J].IEEE Transactions on Parallel and Distributed Systems,1999,10(1):44-61. [4]BAO F,FUNYU Y,HAMADA Y,et al.Reliable broadcasting and secure distributing in channel networks [J].IEICE Transactions on Fundamentals of Electronics,Communications and Computer Sciences,1998,E81-A(5):796-806. [5]BAO F,IGARASHI Y,ÖHRING S R.Reliable broadcasting in product networks [J].Discrete Applied Mathematics,1998,83(1/2/3):3-20. [6]CHEN Y S,CHIANG C Y,CHEN C Y.Multi-node broadcas-ting in all-ported 3-D wormhole-routed torus using an aggregation-then-distribution strategy [J].Journal of Systems Architecture,2004,50(9):575-589. [7]ELHOURANI T,GOPALAN A,RAMASUBRAMANIAN S.IP fast rerouting for multi-link failures [J].IEEE/ACM Tran-sactions on Networking,2016,24(5):3014-3025. [8]GOPALAN A,RAMASUBRAMANIAN S.IP fast reroutingand disjoint multipathrouting with three edge-independent spanning trees [J].IEEE/ACM Transactions on Networking,2016,24(3):1336-1349. [9]PAN Z Y,CHENG B L,FAN J X,et al.A parallel algorithm to construct edge independent spanning trees on the line graphs of conditional bijective connection networks [J].Theoretical Computer Science,2023,942:33-46. [10]ITAI A,RODEH M.The multi-tree approach to reliability in distributed networks [J].Information and Computation,1988,79:43-59. [11]HSIEH S Y,WU C Y.Edge-fault-tolerant Hamiltonicity of locally twisted cubes under conditional edge faults [J].Journal of Combinatorial Optimization,2010,19(1):16-30. [12]ZEHAVI A,ITAI A.Three tree-paths [J].Journal of GraphTheory,1989,13(2):175-188. [13]GOPALANA.On constructing three edge independent spanning trees[EB/OL].https://www.semanticscholar.org/paper/ON-CONSTRUCTING-THREE-EDGE-INDEPENDENT-SPAN-NING-Gopalan/b458a3f665cd41f1ec42fb3cebb5176c369a87ec?p2df. [14]HOYER A,THOMAS R.Four edge-independent spanning trees [J].SIAM Journal on Mathematics,2018,32(1):233-248. [15]ALI A,LEE O.Five edge-independent spanning trees [J].Procedia Computer Science,2023,223:223-230. [16]WANG Y,SHEN H,FAN J X.Edge-independent spanningtrees in augmented cubes [J].Theoretical Computer Science,2017,670:23-32. [17]KIM J S,LEE H O,CHENG E,et al.Independent spanningtrees on even networks [J].Information Sciences,2011,181(13):2892-2905. [18]KIM J S,LEE H O,CHENG E,et al.Optimal independentspanning trees on odd graphs [J].The Journal of Supercompu-ting,2011,56(2):212-225. [19]BAO F,OBOKATA K,IGARASHI Y,et al.Independent spanning trees of product graphs and their construction [J].IEICE Transactions on Fundamentals of Electronics Communications and Computer Sciences,1996,E79-A(11):1894-1903. [20]TANG S M,YANG J S,WANG Y L,et al.Independent spanning trees on multidimensional torus networks [J].IEEE Transactions on Computers,2010,59(1):93-102. [21]DONG Q,WANG X.How many triangles and quadrilaterals are there in an n-dimensional augmented cube [J].Theoretical Computer Science,2019,771:93-98. [22]MANE S A,KANDEKAR S A,WAPHARE B N.Constructing spanning trees in augmented cubes [J].Journal of Parallel and Distributed Computing,2018,122:188-194. [23]CHENG B L,FAN J X,LIN C K,et al.An improved algorithm to construct edge-independent spanning trees in augmented cubes [J].Discrete Applied Mathematics,2020,277:55-70. |
|