Top

The Journal of Supercomputing

Published in:

07-01-2019

Paired many-to-many two-disjoint path cover of balanced hypercubes with faulty edges

Author: Huazhong Lü

Published in: The Journal of Supercomputing | Issue 1/2019

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

search-config

AI-assisted search

Off

Abstract

As a variant of the well-known hypercube, the balanced hypercube \(BH_n\) was proposed as a desired interconnection network topology for parallel computing. It is known that \(BH_n\) is bipartite. Assume that \(S=\{s_1,s_2\}\) and \(T=\{t_1,t_2\}\) are any two sets of vertices in different partite sets of \(BH_n\) (\(n\ge 1\)). It has been proved that there exist two vertex-disjoint \(s_1,t_1\)-path and \(s_2,t_2\)-path of \(BH_n\) covering all vertices of \(BH_n\). In this paper, we prove that there always exist two vertex-disjoint \(s_1,t_1\)-path and \(s_2,t_2\)-path covering all vertices of \(BH_n\) (\(n\ge 2\)) with at most \(2n-3\) faulty edges. The upper bound \(2n-3\) of edge faults can be tolerated is optimal.

previous article High-performance architecture for flow-table lookup in SDN on FPGA

next article Dynamic directory table with victim cache: on-demand allocation of directory entries for active shared cache blocks

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

Arabnia HR, Oliver MA (1986) Fast operations on raster images with SIMD machine architectures. Comput Graphic Forum 5:179–189CrossRef

Arabnia HR (1990) A parallel algorithm for the arbitrary rotation of digitized images using process-and-data-decomposition approach. J Parallel Distrib Comput 10:188–192CrossRef

Arabnia HR, Bhandarkar SM (1996) Parallel stereocorrelation on a reconfigurable multi-ring network. J Supercomput 10:243–269CrossRefMATH

Arabnia HR, Taha TR (1998) A parallel numerical algorithm on a reconfigurable multi-ring network. Telecommun Syst 10:185–202CrossRef

Arabnia HR, Robinson MR (1990) Parallelizing using process-and-aata-decomposition (PADD) approach on a multi-ring transputer network-an example. In: Wagner AS (ed) Transputer research and applications (NATUG 3). IOS Press, Sunnyvale, pp 107–118

Arabnia HR (1993) A transputer-based reconfigurable parallel system. In: Atkins S, Wagner AS (eds) Transputer research and applications (NATUG 6). IOS Press, Vancouver, pp 153–169

Bhandarkar SM, Arabnia HR (1997) Parallel computer vision on a reconfigurable multiprocessor network. IEEE Trans Parallel Distrib Syst 8:292–310CrossRef

Bondy JA, Murty USR (2007) Graph theory. Springer, New YorkMATH

Cai J (2015) An algorithm for Hamiltonian cycles under implicit degree conditions. Ars Comb 121:305–313MathSciNetMATH

10.

Cai J, Li H (2016) Hamilton cycles in implicit 2-heavy graphs. Graphs Comb 32:1329–1337MathSciNetCrossRefMATH

11.

Chen X-B (2016) Paired 2-disjoint path covers of faulty \(k\)-ary \(n\)-cubes. Theor Comput Sci 609:494–499MathSciNetCrossRefMATH

12.

Cheng D, Hao R, Feng Y (2014) Two node-disjoint paths in balanced hypercubes. Appl Math Comput 242:127–142MathSciNetMATH

13.

Dong Q, Zhou J, Fu Y, Gao H (2013) Hamiltonian connectivity of restricted hypercube-like networks under the conditional fault model. Theor Comput Sci 472:46–59MathSciNetCrossRefMATH

14.

Dybizbański J, Szepietowski A (2017) Hamiltonian paths in hypercubes with local traps. Inf Sci 375:258–270CrossRef

15.

Fan J, Lin X, Jia X (2007) Optimal path embeddings of paths with various lengths in twisted cubes. IEEE Trans Parallel Distrib Syst 18(4):511–521CrossRef

16.

Gould RJ (2003) Advances on the Hamiltonian problem—a survey. Graphs Comb 19:7–52MathSciNetCrossRefMATH

17.

Hao R-X, Ru Z, Feng Y-Q (2014) Hamiltonian cycle embedding for fault tolerance in balanced hypercubes. Appl Math Comput 244:447–456MathSciNetMATH

18.

Huang K, Wu J (1997) Fault-tolerant resource placement in balanced hypercubes. Inf Sci 99:159–172MathSciNetCrossRef

19.

Jo S, Park J-H, Chwa K-Y (2013) Paired many-to-many disjoint path covers in faulty hypercubes. Theor Comput Sci 513:1–24MathSciNetCrossRefMATH

20.

Kim S-Y, Park J-H (2013) Paired many-to-many disjoint path covers in recursive circulants \(G(2^m,4)\). IEEE Trans Comput 62(12):2468–2475MathSciNetCrossRefMATH

21.

Leighton FT (1992) Introduction to parallel algorithms and architectures. Morgan Kaufmann Publishers, San MateoMATH

22.

Li P, Xu M (2017) Edge-fault-tolerant edge-bipancyclicity of balanced hypercubes. Appl Math Comput 307:180–192MathSciNetMATH

23.

Lü H, Li X, Zhang H (2012) Matching preclusion for balanced hypercubes. Theor Comput Sci 465:10–20MathSciNetCrossRefMATH

24.

Lü H, Zhang H (2014) Hyper–Hamiltonian laceability of balanced hypercubes. J Supercomput 68:302–314CrossRef

25.

Lü H (2017) On extra connectivity and extra edge-connectivity of balanced hypercubes. Int J Comput Math 94(4):813–820MathSciNetCrossRefMATH

26.

Lü H, Gao X, Yang X (2016) Matching extendability of balanced hypercubes. Ars Comb 129:261–274MathSciNetMATH

27.

Park J-H, Kim H-C, Lim H-S (2006) Many-to-many disjoint path covers in hypercube-like interconnection networks with faulty elements. IEEE Trans Parallel Distrib Syst 17(3):227–240CrossRef

28.

Park J-H, Kim H-C, Lim H-S (2009) Many-to-many disjoint path covers in presence of faulty elements. IEEE Trans Comput 58(4):528–540MathSciNetCrossRefMATH

29.

Tsai C-H (2004) Linear array and ring embeddings in conditional faulty hypercubes. Theor Comput Sci 314:431–443MathSciNetCrossRefMATH

30.

Tsai C-H, Tan JJM, Chuang Y-C, Hsu L-H (2002) Hamiltonian properties of faulty recursive circulant graphs. J Int Netw 3:273–289CrossRef

31.

Wang F, Zhang H (2018) Hamiltonian laceability in hypercubes with faulty edges. Discrete Appl Math 236:438–445MathSciNetCrossRefMATH

32.

Wang S, Zhang S, Yang Y (2014) Hamiltonian path embeddings in conditional faulty \(k\)-ary \(n\)-cubes. Inf Sci 268:463–488MathSciNetCrossRefMATH

33.

Wani MA, Arabnia HR (2003) Parallel edge-region-based segmentation algorithm targeted at reconfigurable multi-ring network. J Supercomput 25:43–62CrossRefMATH

34.

Wu J, Huang K (1997) The balanced hypercube: a cube-based system for fault-tolerant applications. IEEE Trans Comput 46(4):484–490MathSciNetCrossRef

35.

Xu M, Hu H, Xu J (2007) Edge-pancyclicity and Hamiltonian laceability of the balanced hypercubes. Appl Math Comput 189:1393–1401MathSciNetMATH

36.

Yan J, Zhang S, Cai J (2018) Fan-type condition on disjoint cycles in a graph. Discrete Math 341:1160–1165MathSciNetCrossRefMATH

37.

Yang M (2010) Bipanconnectivity of balanced hypercubes. Comput Math Appl 60:1859–1867MathSciNetCrossRefMATH

38.

Yang M (2013) Conditional diagnosability of balanced hypercubes under the PMC model. Inf Sci 222:754–760MathSciNetCrossRefMATH

39.

Yang M (2012) Super connectivity of balanced hypercubes. Appl Math Comput 219:970–975MathSciNetMATH

40.

Zhou Q, Chen D, Lü H (2015) Fault-tolerant Hamiltonian laceability of balanced hypercubes. Inf Sci 300:20–27MathSciNetCrossRefMATH

41.

Zhou J-X, Wu Z-L, Yang S-C, Yuan K-W (2015) Symmetric property and reliability of balanced hypercube. IEEE Trans Comput 64(3):871–876MathSciNetCrossRefMATH

42.

Zhou J-X, Kwak J, Feng Y-Q, Wu Z-L (2017) Automorphism group of the balanced hypercube. Ars Math Contemp 12:145–154MathSciNetCrossRefMATH

Title: Paired many-to-many two-disjoint path cover of balanced hypercubes with faulty edges
Author: Huazhong Lü
Publication date: 07-01-2019
Publisher: Springer US
Published in: The Journal of Supercomputing / Issue 1/2019
Print ISSN: 0920-8542
Electronic ISSN: 1573-0484
DOI: https://doi.org/10.1007/s11227-018-02734-0

Springer Professional

Abstract

Please log in to get access to your license.

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

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Springer Professional "Wirtschaft+Technik"

Other articles of this Issue 1/2019

CHAOS: a parallelization scheme for training convolutional neural networks on Intel Xeon Phi

A method for achieving provable data integrity in cloud computing

Detection of centerline crossing in abnormal driving using CapsNet

Mesh-of-Torus: a new topology for server-centric data center networks

A domain-divided configurable security model for cloud computing-based telecommunication services

High-performance architecture for flow-table lookup in SDN on FPGA

Premium Partner