nach oben

The Journal of Supercomputing

Erschienen in:

09.06.2021

Node-to-set disjoint paths problem in cross-cubes

verfasst von: Xi Wang, Jianxi Fan, Shukui Zhang, Jia Yu

Erschienen in: The Journal of Supercomputing | Ausgabe 1/2022

Einloggen

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

search-config

KI-gestützte Suche

Aus

Abstract

Hypercubes are popular topologies of massive multiprocessor systems due to their super properties. Cross-cubes are significant variations of hypercubes and they have smaller diameters and higher fault-tolerant capability than hypercubes at the same dimensions. In this paper, we construct node-to-set disjoint paths of an n-dimensional cross-cube, \(C_{n}\), whose maximum length is limited by \(2n-3\). Furthermore, we propose an \(O(N \text {log}^{2}N)\) algorithm with a view to finding node-to-set disjoint paths of \(C_{n}\), where N is the node number of \(C_n\). And we also present the simulation results for the maximal length of disjoint paths obtained by our algorithm.

Vorheriger Artikel Maximum Network Lifetime Problem with Time Slots and coverage constraints: heuristic approaches

Nächster Artikel Efficient detection of silent data corruption in HPC applications with synchronization-free message verification

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

Fu H, Liao J, Yang J et al (2016) The sunway TaihuLight supercomputer: system and applications. Sci China Inform Sci 59(7):072001CrossRef

Harary F, Hayes JP, Wu H-J (1988) A survey of the theory of hypercube graphs. Comput Math Appl 15(4):277–289MathSciNetCrossRef

Haq E (1991) Cross-cube: a new fault tolerant hypercube-based network. In: Proceedings of fifth international parallel processing symposium, pp 471–474

Efe K (1992) The crossed cube architecture for parallel computation. IEEE Comput Archit Lette 3(05):513–524

Cull P, Larson SM (1995) The Möbius cubes. IEEE Trans Comput 44(5):647–659MathSciNetCrossRef

Zhou W, Fan J, Jia X, Zhang S (2011) The spined cube: a new hypercube variant with smaller diameter. Inform Process Lett 111(12):561–567MathSciNetCrossRef

Wang X, Fan J, Jia X, Lin C-K (2016) An efficient algorithm to construct disjoint path covers of DCell networks. Theor Comput Sci 609(1):197–210MathSciNetCrossRef

Wang X, Fan J, Lin C-K, Jia X (2016) Vertex-disjoint paths in DCell networks. J Parall Distrib Comput 96:38–44CrossRef

Kaneko K, Bossard A (2017) A set-to-set disjoint paths routing algorithm in tori. Int J Netw Comput 7(2):173–186

10.

Bossard A, Kaneko K (2014) Time optimal node-to-set disjoint paths routing in hypercubes. J Inform Sci Eng 30(4):1087–1093MathSciNet

11.

Kocik D, Hirai Y, Kaneko K (2016) Node-to-set disjoint paths problem in a Möbius cube. IEICE Trans Inform Syst 99(3):708–713CrossRef

12.

Gu Q, Peng S (1997) Node-to-set disjoint paths problem in star graphs. Inform Process Lett 62(4):201–207MathSciNetCrossRef

13.

Kaneko K, Suzuki Y (2003) Node-to-set disjoint paths problem in pancake graphs. IEICE Trans Inform Syst 86(9):1628–1633

14.

Kaneko K (2003) An algorithm for node-to-set disjoint paths problem in burnt pancake graphs. IEICE Trans Inform Syst 86(12):2588–2594

15.

Bossard A, Kaneko K (2012) Node-to-set disjoint-path routing in hierarchical cubic networks. Comput J 55(12):1440–1446CrossRef

16.

Bossard A, Kaneko K, Peng S (2011) A new node-to-set disjoint-path algorithm in perfect hierarchical hypercubes. Comput J 54(8):1372–1381CrossRef

17.

Bossard A, Kaneko K, Peng S (2011) Node-to-set disjoint-path routing in perfect hierarchical hypercubes. Procedia Comput Sci 4:442–451CrossRef

18.

Ling S, Chen W (2013) Node-to-set disjoint paths in biswapped networks. Comput J 57(7):953–967CrossRef

19.

Diestel R (2012) Graph theory, 4th edn, vol 173. In: Graduate texts in mathematics. Springer

20.

Wang X, He F, Zhang S (2018) A restricted fault-free unicast algorithm in cross-cubes. J Southwest China Norm Univ 43(9):57–65 in Chinese

21.

Bossard A, Kaneko K (2012) The set-to-set disjoint-path problem in perfect hierarchical hypercubes. Comput J 55(6):769–775CrossRef

22.

Bossard A, Kaneko K (2016) Set-to-set disjoint paths routing in torus-connected cycles. IEICE Trans Inform Syst 99(11):2821–2823CrossRef

23.

Lü H (2019) Paired many-to-many two-disjoint path cover of balanced hypercubes with faulty edges. J Supercomput 75(1):400–424CrossRef

24.

Park J-H, Kim J-H, Lim H-S (2019) Disjoint path covers joining prescribed source and sink sets in interval graphs. Theor Comput Sci 776:125–137MathSciNetCrossRef

25.

Cheng B, Wang D, Fan J (2017) Constructing completely independent spanning trees in crossed cubes. Disc Appl Math 219:100–109MathSciNetCrossRef

26.

Fan J, Jia X, Cheng B, Yu J (2011) An efficient fault-tolerant routing algorithm in bijective connection networks with restricted faulty edges. Theor Comput Sci 412(29):3440–3450MathSciNetCrossRef

Titel: Node-to-set disjoint paths problem in cross-cubes
verfasst von: Xi Wang
Jianxi Fan
Shukui Zhang
Jia Yu
Publikationsdatum: 09.06.2021
Verlag: Springer US
Erschienen in: The Journal of Supercomputing / Ausgabe 1/2022
Print ISSN: 0920-8542
Elektronische ISSN: 1573-0484
DOI: https://doi.org/10.1007/s11227-021-03872-8

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

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

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Springer Professional "Wirtschaft+Technik"

Weitere Artikel der Ausgabe 1/2022

A generic construction to build simple oblivious transfer protocols from homomorphic encryption schemes

Queue-priority optimized algorithm: a novel task scheduling for runtime systems of application integration platforms

Efficient detection of silent data corruption in HPC applications with synchronization-free message verification

Maximum Network Lifetime Problem with Time Slots and coverage constraints: heuristic approaches

The societal communication of the Q&A community on topic modeling

Revisiting split tiling for stencil computations in polyhedral compilation

Premium Partner