Computer Science

Computer Science ›› 2024, Vol. 51 ›› Issue (9): 346-356.doi: 10.11896/jsjkx.230700041

• Computer Network • Previous Articles     Next Articles

Parallel Construction of Edge-independent Spanning Trees in Augmented Cubes

LI Xiajing1,2, CHENG Baolei1,2, FAN Jianxi1, WANG Yan1,2, LI Xiaorui1,2   

  1. 1 School of Computer Science and Technology,Soochow University,Suzhou,Jiangsu 215006,China
    2 Provincial Key Laboratory for Computer Information Processing Technology,Soochow University,Suzhou,Jiangsu 215006,China
  • Received:2023-07-06 Revised:2023-11-02 Online:2024-09-15 Published:2024-09-10
  • About author:LI Xiajing,born in 1999,postgraduate,is a member of CCF( No.J1607G).Her main research interests include parallel and distributed systems and graph algorithms.
    CHENG Baolei,born in 1979,professor,is a member of CCF( No.16200S).His main research interests include parallel and distributed systems,algorithms,interconnection architectures and software testing.
  • Supported by:
    National Natural Science Foundation of China(62272333,62172291),Jiangsu Province Department of Education Future Network Research Fund Project(FNSRFP-2021-YB-39) and Project Funded by the Priority Academic Program Development of Jiangsu Higher Education Institutions.

PDF (PC)

320

Abstract: In recent years,more and more research work is being conducted around interconnected networks.Independent spanning trees(ISTs) can be used in reliable transmission,parallel transmission,safe distribution of information,and parallel diagnosis of fault servers,and have attracted many researchers' attention.In network communication,such as one-to-all broadcasting,reliable communication,multi-node broadcasting,fault-tolerant broadcasting,secure message distribution,and IP fast rerouting,edge-independent spanning trees(EISTs) play a significant role.The augmented cube of n dimension AQn is a node-symmetric variation of the n-dimensional hypercube Qn,it has some embeddable properties that the hypercube and its variants do not have.However,the current EISTs construction methods in augmented cubes are serial construction.This paper first proposes parallel algorithms for constructing 2n－1 trees rooted at any node in AQn.Then,it proves that the 2n－1 trees obtained by algorithms are EISTs with the height n,and the algorithms' time complexity is O(N),where N equals the number of nodes in AQn.Finally,its accuracy is verified by simulation experiment.

Key words: Interconnection network, Augmented cube, Edge-independent spanning trees, Parallel algorithm, Height

CLC Number: 

  • TP311.12
[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.
[1] TU Yuanjie, CHENG Baolei, WANG Yan, HAN Yuejuan, FAN Jianxi. g-Good-Neighbor Conditional Diagnosability and g-Extra Conditional Diagnosability of Hypercubes Under Symmetric PMC Model [J]. Computer Science, 2024, 51(9): 103-111.
[2] PU Bin, LIANG Zhengyou, SUN Yu. Monocular 3D Object Detection Based on Height-Depth Constraint and Edge Fusion [J]. Computer Science, 2024, 51(8): 192-199.
[3] LU Chunhai, XU Xinhai, ZHANG Shuai, LI Hao. Study on Volume Cloud Simulation Based on Weather Data and Multi-noise Fusion [J]. Computer Science, 2023, 50(6): 236-242.
[4] XU Jia-qing, HU Xiao-yue, TANG Fu-qiao, WANG Qiang, HE Jie. Detecting Blocking Failure in High Performance Interconnection Networks Based on Random Forest [J]. Computer Science, 2021, 48(6): 246-252.
[5] FENG Kai, MA Xin-yu. Subnetwork Reliability of (n,k)-bubble-sort Networks [J]. Computer Science, 2021, 48(4): 43-48.
[6] LI Yu-rong, LIU Jie, LIU Ya-lin, GONG Chun-ye, WANG Yong. Parallel Algorithm of Deep Transductive Non-negative Matrix Factorization for Speech Separation [J]. Computer Science, 2020, 47(8): 49-55.
[7] FENG Kai, LI Jing. Study on Subnetwork Reliability of k-ary n-cubes [J]. Computer Science, 2020, 47(7): 31-36.
[8] SHI Teng and SHI Hai-zhong. Model of Cartesian Product of Modulo p Residual Class Addition Group for Interconnection Networks [J]. Computer Science, 2020, 47(6A): 299-304.
[9] FU Jian,KONG Fang. Coreference Resolution Incorporating Structural Information [J]. Computer Science, 2020, 47(3): 231-236.
[10] LI Fang,LI Zhi-hui,XU Jin-xiu,FAN Hao,CHU Xue-sen,LI Xin-liang. Research on Adaptation of CFD Software Based on Many-core Architecture of 100P Domestic Supercomputing System [J]. Computer Science, 2020, 47(1): 24-30.
[11] NI Hong, LIU Xin. Many-core Optimization for Sparse Triangular Solver Under Unstructured Grids [J]. Computer Science, 2019, 46(6A): 518-522.
[12] ZHU Chao, WU Su-ping. Parallel Harris Feature Point Detection Algorithm [J]. Computer Science, 2019, 46(11A): 289-293.
[13] ZHOU Jie and LI Wen-jing. Research on Parallel Algorithm of Petri Net Based on Three-layer Mixed Programming Model [J]. Computer Science, 2017, 44(Z11): 586-591.
[14] LIN Cheng-kuan, ZHAO Yuan, FAN Jian-xi and CHENG Bao-lei. Research on Completely Independent Spanning Trees Based on Degree of Vertices [J]. Computer Science, 2017, 44(6): 94-96.
[15] ZHU Kai-long, LU Yu-liang and ZHANG Yan-qing. Study on Calculation Method for Internet Topological Parameters Based on MapReduce [J]. Computer Science, 2017, 44(6): 80-82.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
No Suggested Reading articles found!
渝ICP备16013121号-4
Add:18# Honghu West Rd., Yubei ,Chongqing,China    Post Code: 401121
Tel: 023-63500828/023-67039612/023-67039623
E-mail: jsjkx12@163.com
Powered by Beijing Magtech Co., Ltd.