Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Bücher
Zeitschriften
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
SLX-Digitalkonferenz: Zukunftswerkstatt 2024

Mehr Umsatz mit Top-Kontakten

Am 7. Mai erfahren Sie, wie Vertriebsteams Leadgenerierung, Leadnurturing und Leadstrategien effizient steuern können.
Erweiterte Suche
Anmelden
nach oben
The Journal of Supercomputing
Erschienen in: The Journal of Supercomputing 4/2023

22.09.2022

Three edge-disjoint Hamiltonian cycles in crossed cubes with applications to fault-tolerant data broadcasting

verfasst von: Kung-Jui Pai, Ro-Yu Wu, Sheng-Lung Peng, Jou-Ming Chang

Erschienen in: The Journal of Supercomputing | Ausgabe 4/2023

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

Multiple edge-disjoint Hamiltonian cycles (EDHCs) provide the advantages of data broadcast in parallel and edge fault-tolerance in network communications. This paper investigates how to construct more EDHCs in a hypercube-variant network called crossed cube, denoted as \(CQ_n\). The topology of \(CQ_n\) has more wealth than normal hypercubes in network properties, e.g., it has about half of the diameter of a hypercube with the same dimension. Then, we obtain the following results in this paper: (1) We first provide the construction of three EDHCs in \(CQ_6\). (2) According to the recursive structure of \(CQ_n\), we prove by induction that there exist also three EDHCs in \(CQ_n\) for \(n\geqslant 7\). (3) Finally, we evaluate the performance of data broadcasting by simulation through three EDHCs and compare it against the best previous result in [18] using two EDHCs. In particular, our findings significantly improved the average success rate in edge fault-tolerant data broadcasting and two specific metrics concerning the broadcasting delivery time (latency).
Vorheriger Artikel A sliced architecture using novel configurable logic modules in quantum dot cellular automata for application of field-programmable gate arrays
Nächster Artikel Evaluation of e-learners’ concentration using recurrent neural networks

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

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!

Jetzt informieren

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!

Jetzt informieren

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!

Jetzt informieren
Literatur
1.
Lee S, Shin K (1994) Interleaved all-to-all reliable broadcast on meshes and hypercubes. IEEE Trans Parallel Distrib Syst 5(5):449–458CrossRef
2.
Leighton FT (1992) Introduction to parallel algorithms and architecture: arrays, trees, Hypercubes. Morgan Kaufmann, San Mateo, CalifMATH
3.
Lin T-J, Hsieh S-Y, Juan JS-T (2012) Embedding cycles and paths in product networks and their applications to multiprocessor systems. IEEE Trans Parallel Distrib Syst 23(6):1081–1089CrossRef
4.
Wang N-C, Yen C-P, Chu C-P (2005) Multicast communication in wormhole-routed symmetric networks with Hamiltonian cycle model. J Syst Arch 51(3):165–183CrossRef
5.
Bae MM, Bose B (2003) Edge disjoint Hamiltonian cycles in \(k\)-ary \(n\)-cubes and hypercubes. IEEE Trans Comput 52(10):1271–1284CrossRef
6.
Rowley R, Bose B (1991) Edge disjoint Hamiltonian cycles in de Bruijn networks. In: Proceedings of the 6th Distributed Memory Computing Conference, Portland, USA, pp 707–709
7.
Xu J-M, Ma M (2009) A survey on cycle and path embedding in some networks. Front Math China 4(2):217–252MATHCrossRef
8.
Garey MR, Johnson DS (1979) Computers and intractability: a guide to the theory of NP-completeness. Freeman, San FranciscoMATH
9.
Barth D, Raspaud A (1994) Two edge-disjoint Hamiltonian cycles in the butterfly graph. Inf Process Lett 51(4):175–179MATHCrossRef
10.
Albader B, Bose B (2016) Edge disjoint Hamiltonian cycles in Gaussian networks. IEEE Trans Comput 65(1):315–321MATHCrossRef
11.
Hung R-W (2011) Embedding two edge-disjoint Hamiltonian cycles into locally twisted cubes. Theor Comput Sci 412:4747–4753MATHCrossRef
12.
Li S-Y, Chang J-M, Pai K-J (2020) A parallel algorithm for constructing two edge-disjoint hamiltonian cycles in locally twisted cubes. In: Proceedings of International Computer Conference (ICS 2020), Tainan, Taiwan, 17–19 Dec, pp 116–119
13.
Lü H, Wu T (2019) Edge-disjoint Hamiltonian cycles of balanced hypercubes. Inf Process Lett 144:25–30MATHCrossRef
14.
Hung R-W (2012) Constructing two edge-disjoint Hamiltonian cycles and two-equal path cover in augmented cubes. IAENG Int’l J Comput Sci 39(1):42–49
15.
Hung R-W, Chan S-J, Liao C-C (2012) Embedding two edge disjoint Hamiltonian cycles and two equal node disjoint cycles into twisted cubes. In: Proceedings of International Multi-Conference Engineers and Computer Scientists (IMECS 2012), Hong Kong, 14–6 Mar, pp 362–367
16.
Wang Y, Fan J, Liu W, Wang X (2013) Embedding two edge-disjoint Hamiltonian cycles into parity cubes. Appl Mech Mater 336–338:2248–2251
17.
Pai K-J (2020) A parallel algorithm for constructing two edge-disjoint Hamiltonian cycles in crossed cubes. In: Proceedings of 14th International Conference on Algorithmic Applications in Management (AAIM 2020). Lecture Notes in Computer Science, 12290: 448–455
18.
Hung R-W (2015) The property of edge disjoint Hamiltonian cycles in transposition networks and hypercube like networks. Discrete Appl Math 181:109–122MATHCrossRef
19.
Hussain ZA, Bose B, Al-Dhelaan A (2015) Edge disjoint Hamiltonian cycles in Eisenstein-Jacobi networks. J Parallel Distrib Comput 86:62–70CrossRef
20.
Petrovic V, Thomassen C (2006) Edge disjoint Hamiltonian cycles in hypertournaments. J Graph Theory 51(1):49–52MATHCrossRef
21.
Huang C-H, Fang J-F, Yang C-Y (2004) Edge-disjoint Hamiltonian cycles of WK-recursive networks. In: Proceedings of 7th International Workshop on Applied Parallel Computing (PARA 2004). Lecture Notes in Computer Science, 3732: 1009–1104
22.
Hussain ZA, Bose B, Al-Dhelaan A (2014) Generalized hypercubes: edge-disjoint Hamiltonian cycles and Gray codes. IEEE Trans Comput 63(2):375–382MATHCrossRef
23.
Chen H-C, Kung T-L, Zou Y-H, Mao H-W (2015) The fault-tolerant Hamiltonian problems of crossed cube with path faults. IEICE Trans Infom Syst E98–D(12):2116–2122CrossRef
24.
Huang W-T, Chuang Y-C, Tan JJ-M, Hsu L-H (2002) On the fault-tolerant Hamiltonicity of faulty crossed cubes. IEICE Trans Fundam Electron Commun Comput Sci E85–A(6):1359–1370
25.
Wang D (2008) On embedding hamiltonian cycles in crossed cubes. IEEE Trans Parallel Distrib Syst 19(3):334–346CrossRef
26.
Xu X, Zhang H, Wang Z, Zhang Q, Zhang P (2021) (\(n-2\))-fault-tolerant edge-pancyclicity of crossed cubes \(CQ_n\). Int J Found Comput Sci 32(3):289–304CrossRef
27.
Fu J-S, Hung H-S, Chen G-H (2009) Embedding fault-free cycles in crossed cubes with conditional link faults. J Supercomput 49(2):219–233CrossRef
28.
Hung H-S, Fu J-S, Chen G-H (2007) Fault-free Hamiltonian cycles in crossed cubes with conditional link faults. Inf Sci 177:5664–5674MATHCrossRef
29.
Chen H-C (2018) The panpositionable panconnectedness of crossed cubes. J Supercomput 74(6):2638–2655CrossRef
30.
Chen H-C, Kung T-L, Hsu L-H (2011) Embedding a Hamiltonian cycle in the crossed cube with two required vertices in the fixed positions. Appl Math Comput 217(24):10058–10065MATH
31.
Chang J-M, Wang J-D, Yang J-S, Pai K-J (2014) A comment on “independent spanning trees in crossed cubes’’. Inf Process Lett 114(12):734–739MATHCrossRef
32.
Cheng B, Fan J, Jia X, Wang J (2013) Dimension-adjacent trees and parallel construction of independent spanning trees on crossed cubes. J Parallel Distrib Comput 73(5):641–652MATHCrossRef
33.
Cheng B, Fan J, Jia X, Zhang S (2013) Independent spanning trees in crossed cubes. Inf Sci 233:276–289MATHCrossRef
34.
Cheng B, Fan J, Lyu Q, Zhou J, Liu Z (2018) Constructing independent spanning trees with height \(n\) on the \(n\)-dimensional crossed cube. Future Gener Comput Syst 87:404–415CrossRef
35.
Cheng B, Wang D, Fan J (2017) Constructing completely independent spanning trees in crossed cubes. Discrete Appl Math 219:100–109MATHCrossRef
36.
Pai K-J, Chang J-M (2016) Constructing two completely independent spanning trees in hypercube-variant networks. Theor Comput Sci 652:28–37MATHCrossRef
37.
Pai K-J, Chang R-S, Wu R-Y, Chang J-M (2019) A two-stages tree-searching algorithm for finding three completely independent spanning trees. Theor Comput Sci 784:65–74MATHCrossRef
38.
Pai K-J, Chang R-S, Wu R-Y, Chang J-M (2020) Three completely independent spanning trees of crossed cubes with application to secure-protection routing. Inf Sci 541:516–530MATHCrossRef
39.
Wang X, Fan J, Zhang S, Yu J (2022) Node-to-set disjoint paths problem in cross-cubes. J Supercomput 78(1):1356–1380CrossRef
40.
Fan J (2002) Diagnosability of crossed cubes under the comparison diagnosis model. IEEE Trans Parallel Distrib Syst 13(10):1099–1104CrossRef
41.
Guo J, Li D, Lu M (2019) The \(g\)-good-neighbor conditional diagnosability of the crossed cubes under the PMC and MM* model. Theor Comput Sci 755:81–88MATHCrossRef
42.
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
43.
Efe K, Blackwell PK, Slough W, Shiau T (1994) Topological properties of the crossed cube architecture. Parallel Comput 20(12):1763–1775MATHCrossRef
44.
Efe K (1992) The crossed cube architecture for parallel computation. IEEE Trans Parallel Distrib Syst 3(5):513–524CrossRef
45.
Fragopoulou P, Akl SG (1996) Edge-disjoint spanning trees on the star network with applications to fault tolerance. IEEE Trans Comput 45(2):174–185MATHCrossRef
46.
Chen Y-S, Juang T-Y, Tseng E-H (2000) Efficient broadcasting in an arrangement graph using multiple spanning trees. IEICE Trans Fundam Electron Commun Comput Sci E83–A(1):139–149MATH
47.
Yang J-S, Chan H-C, Chang J-M (2011) Broadcasting secure messages via optimal independent spanning trees in folded hypercubes. Discrete Appl Math 159:1254–1263MATHCrossRef
Metadaten
Titel
Three edge-disjoint Hamiltonian cycles in crossed cubes with applications to fault-tolerant data broadcasting
verfasst von
Kung-Jui Pai
Ro-Yu Wu
Sheng-Lung Peng
Jou-Ming Chang
Publikationsdatum
22.09.2022
Verlag
Springer US
Erschienen in
The Journal of Supercomputing / Ausgabe 4/2023
Print ISSN: 0920-8542
Elektronische ISSN: 1573-0484
DOI
https://doi.org/10.1007/s11227-022-04825-5

Weitere Artikel der Ausgabe 4/2023

The Journal of Supercomputing 4/2023 Zur Ausgabe

OriginalPaper

Quantifying DDS-cerberus network control overhead

Correction

Correction to: ReNo: novel switch architecture for reliability improvement of NoCs

OriginalPaper

Evaluation of e-learners’ concentration using recurrent neural networks

OriginalPaper

HBI-LB: A Dependable Fault-Tolerant Load Balancing Approach for Fog based Internet-of-Things Environment

OriginalPaper

Building a Lucy hybrid model for grocery sales forecasting based on time series

OriginalPaper

A randomized algorithm for the wait-free consensus problem

Premium Partner

    Bildnachweise