Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
The Journal of Supercomputing
Published in: The Journal of Supercomputing 2/2024

24-07-2023

Constructing edge-disjoint spanning trees in several cube-based networks with applications to edge fault-tolerant communication

Authors: Huanwen Zhang, Yan Wang, Jianxi Fan, Yuejuan Han, Baolei Cheng

Published in: The Journal of Supercomputing | Issue 2/2024

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

If a set of spanning trees of a graph do not share any edge with each other, they are called edge-disjoint spanning trees (for short EDSTs), which have widespread practical applications, such as fault-tolerant broadcasting, the distributed algorithms against Man-in-the-Middle attacks, the efficient collective communication algorithms, and so on. Crossed cubes, folded cubes, and folded crossed cubes, as three important variations of hypercubes, are optimized in terms of communication efficiency and fault tolerance of networks. In this paper, we propose a recursive algorithm to construct the maximum number of EDSTs in the three kinds of cube-based networks. Additionally, relying on the resulting EDSTs, the performance of one-to-one communication and one-to-all communication with edge failures are evaluated by simulation results in folded crossed cubes.
previous article Disruption mitigation in the semiconductors supply chain by using public blockchains
next article Efficient facial expression recognition framework based on edge computing

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now
Literature
1.
Chen G, Cheng B, Wang D (2021) Constructing completely independent spanning trees in data center network based on augmented cube. IEEE Trans Parallel Distrib Syst 32(3):665–673CrossRef
2.
Andújar FJ, Coll S, Alonso M, Martínez J-M, López P, Sánchez JL, Alfaro FJ (2023) Energy efficient HPC network topologies with on/off links. Futur Gener Comput Syst 139:126–138CrossRef
3.
Li J, Ling B (2018) Symmetric graphs and interconnection networks. Futur Gener Comput Syst 83:461–467CrossRef
4.
Pan Z, Cheng B, Fan J, Wang Y, Li X (2023) A parallel algorithm to construct edge independent spanning trees on the line graphs of conditional bijective connection networks. Theor Comput Sci 942:33–46MathSciNetCrossRef
5.
Saad Y, Schultz MH (1988) Topological properties of hypercubes. IEEE Trans Comput 37(7):867–872CrossRef
6.
Efe K (1991) A variation on the hypercube with lower diameter. IEEE Trans Comput 40(11):1312–1316CrossRef
7.
Chang C-P, Sung T-Y, Hsu L-H (2000) Edge congestion and topological properties of crossed cubes. IEEE Trans Parallel Distrib Syst 11(1):64–80CrossRef
8.
Hung R-W (2015) The property of edge-disjoint hamiltonian cycles in transposition networks and hypercube-like networks. Discret Appl Math 181:109–122MathSciNetCrossRef
9.
Cheng B, Fan J, Lyu Q, Zhou J, Liu Z (2018) Constructing independent spanning trees with height \(n\) on the \(n\)-dimensional crossed cube. Futur Gener Comput Syst 87:404–415CrossRef
10.
Pan Z, Cheng D (2020) Structure connectivity and substructure connectivity of the crossed cube. Theor Comput Sci 824–825(5):67–80MathSciNetCrossRef
11.
Zhang Y-Q (2002) Folded-crossed hypercube: a complete interconnection network. J Syst Archit 47(11):917–922CrossRef
12.
Guo L (2017) Reliability analysis of hypercube networks and folded hypercube networks. WSEAS Trans Math 16:331–338
13.
Lin Y, Lin L, Huang Y, Wang J (2021) The \(t/s\)-diagnosability and \(t/s\)-diagnosis algorithm of folded hypercube under the PMC/MM* model. Theor Comput Sci 887:85–98CrossRef
14.
Lai C-N (2021) Optimal node-disjoint paths in folded hypercubes. J Parallel Distribut Comput 147:100–107CrossRef
15.
Pai K-J, Chang J-M, Yang J-S (2016) Vertex-transitivity on folded crossed cubes. Inform Process Lett 116(11):689–693MathSciNetCrossRef
16.
17.
Guo H, Sabir E, Mamut A (2022) The \(g\)-extra connectivity of folded crossed cubes. J Parallel Distribut Comput 166:139–146CrossRef
18.
Ho C-T (1990) Full bandwidth communications for folded hypercubes. In: Proceedings of the 1990 International Conference on Parallel Processing, pp. 276–280
19.
Yang J-S, Chang J-M, Chan H (2009) Independent spanning trees on folded hypercubes. In: The 10th International Symposium on Pervasive Systems, Algorithms, and Networks, pp. 601–605
20.
21.
Fragopoulou P, Akl SG (1996) Edge-disjoint spanning trees on the star network with applications to fault tolerance. IEEE Trans Comput 45(2):174–185CrossRef
22.
Touzene A, Day K, Monien B (2005) Edge-disjoint spanning trees for the generalized butterfly networks and their applications. J Parallel Distribut Comput 65(11):1384–1396CrossRef
23.
Yang J-S, Chan H-C, Chang J-M (2011) Broadcasting secure messages via optimal independent spanning trees in folded hypercubes. Discret Appl Math 159(12):1254–1263MathSciNetCrossRef
24.
Oliva G, Cioaba S, Hadjicostis CN (2018) Distributed calculation of edge-disjoint spanning trees for robustifying dstributed algorithms against Man-in-the-Middle attacks. IEEE Trans Control Netw Syst 5(4):1646–1656MathSciNetCrossRef
25.
Libeskind-Hadas R, Mazzoni D, Rajagopalan R (1998) Tree-based multicasting in wormhole-routed irregular topologies. In: Proceedings of the First Merged International Parallel Processing Symposium and Symposium on Parallel and Distributed Processing, pp. 244–249
26.
Wang Y, Cheng B, Fan J, Qian Y, Jiang R (2021) An algorithm to construct completely independent spanning trees in line graphs. Comput J 65(12):2979–2990MathSciNetCrossRef
27.
Li X-Y, Lin W, Chang J-M, Jia X (2022) Transmission failure analysis of multi-protection routing in data center networks with heterogeneous edge-core servers. IEEE/ACM Trans Netw 30(4):1689–1702CrossRef
28.
Wang Y, Cheng B, Qian Y, Wang D (2022) Constructing completely independent spanning trees in a family of line-graph-based data center networks. IEEE Trans Comput 71(5):1194–1203CrossRef
29.
Ku S-C, Wang B-F, Hung T-K (2003) Constructing edge-disjoint spanning trees in product networks. IEEE Trans Parallel Distrib Syst 14(3):213–221CrossRef
30.
31.
Ma X, Wu B, Jin X (2018) Edge-disjoint spanning trees and the number of maximum state circles of a graph. J Comb Optim 35(4):997–1008MathSciNetCrossRef
32.
Gu X, Lai H-J, Li P, Yao S (2016) Edge-disjoint spanning trees, edge connectivity, and eigenvalues in graphs. J Graph Theory 81(1):16–29MathSciNetCrossRef
33.
Wang X, Fan J, Lin C-K, Zhou J, Liu Z (2018) BCDC: a high-performance, server-centric data center network. J Comput Sci Technol 33:400–416MathSciNetCrossRef
Metadata
Title
Constructing edge-disjoint spanning trees in several cube-based networks with applications to edge fault-tolerant communication
Authors
Huanwen Zhang
Yan Wang
Jianxi Fan
Yuejuan Han
Baolei Cheng
Publication date
24-07-2023
Publisher
Springer US
Published in
The Journal of Supercomputing / Issue 2/2024
Print ISSN: 0920-8542
Electronic ISSN: 1573-0484
DOI
https://doi.org/10.1007/s11227-023-05546-z

Other articles of this Issue 2/2024

The Journal of Supercomputing 2/2024 Go to the issue

Correction

Correction to: Using a privacy‑enhanced authentication process to secure IoT‑based smart grid infrastructures

OriginalPaper

DG-means: a superior greedy algorithm for clustering distributed data

OriginalPaper

An integrative extraction approach for index-tracking portfolio construction and forecasting under a deep learning framework

OriginalPaper

Feed-forward ANN and traditional machine learning-based prediction of biogas generation rate from meteorological and organic waste parameters

OriginalPaper

Computer-aided diagnostic model for retinal vascular diseases using graph-based attention mechanism

OriginalPaper

Research streams and open challenges in the metaverse

Premium Partner

    Image Credits