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 1/2015

01.01.2015

Embedding complete binary trees into parity cubes

verfasst von: Zhao Liu, Jianxi Fan, Xiaohua Jia

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

Einloggen

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

search-config
loading …

Abstract

The complete binary tree as an important network structure has long been investigated for parallel and distributed computing, which has many nice properties and used to be embedded into other interconnection architectures. The parity cube is an important variant of the hypercube. It has many attractive features superior to those of the hypercube. In this paper, we prove that the complete binary tree with \(2^n-1\) vertices can be embedded with dilation 1, congestion 1, load 1 into the \(n\)-dimensional parity cube \(PQ_n\) and expansion tending to 1. Furthermore, we provide an \(O(NlogN)\) algorithm to construct the complete binary tree with \(2^n-1\) vertices in \(PQ_n\), where \(N\) denotes the number of vertices in \(PQ_n\) and \(n\ge 1\).
Nächster Artikel On the computational power of WECPAR

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
Anhänge
Nur mit Berechtigung zugänglich
Literatur
1.
2.
Chaudhary V, Aggarwal JK (1990) Generalized mapping of parallel algorithms onto parallel architectures. In: Proceedings of the 1990 international conference on parallel processing, vol 2, pp 137–141
3.
Hsu H-C, Li T-K, Tan JJM, Hsu L-H (2004) Fault Hamiltonicity and Fault Hamiltonian connectivity of the arrangement graphs. IEEE Trans Comput 53(1):39–53CrossRefMathSciNet
4.
Patel A, Kusalik A, McCrosky C (2000) Area-efficient VLSI layouts for binary hypercubes. IEEE Trans Comput 49(2):160–169CrossRefMathSciNet
5.
Yang M-C, Tan JJM, Hsu L-H (2007) Highly fault-tolerant cycle embeddings of hypercubes. J Syst Architect 53:227–232CrossRef
6.
Xu JM (2010) Topological structure and analysis of interconnection networks. Springer Publishing Company, Incorporated
7.
Bossard A, Kaneko K (2014) k-pairwise disjoint paths routing in perfect hierarchical hypercubes. J Supercomput 67(2):485–495CrossRef
8.
Keshavarz-Kohjerdi F, Bagheri A (2013) An efficient parallel algorithm for the longest path problem in meshes. J Supercomput 65(2):723–741CrossRef
9.
Fan J, Jia X, Lin X (2007) Optimal embeddings of paths with various lengths in twisted cubes. IEEE Trans Parallel Distrib Syst 18(4):511–521CrossRef
10.
11.
12.
Shih Y-K, Chuang H-C, Kao S-S, Tan JJM (2010) Mutually independent Hamiltonian cycles in dual-cubes. J Supercomput 54(2):239–251CrossRef
13.
Su H, Chen S-Y, Kao S-S (2012) Mutually independent Hamiltonian cycles in alternating group graphs. J Supercomput 61(3):560–571CrossRef
14.
Chen Y, Shen H (2011) Embedding meshes and tori on double-loop networks of the same size. IEEE Trans Comput 60(8):1157–1168CrossRefMathSciNet
15.
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
16.
Liu L, Ming A, Ma H, Zhang X (2012) A binary-classification-tree based framework for distributed target classification in multimedia sensor networks. IEEE INFOCOM, pp 594–602
17.
Vilaplana V, Marques F, Salembier P (2008) Binary partition trees for object detection. IEEE Trans Image Process 17(11):2201–2216CrossRefMathSciNet
18.
Zheng S, Yang M (2007) Algorithm-hardware codesign of fast parallel round-robin arbiters. IEEE Trans Parallel Distrib Syst 18(1):84–95CrossRef
19.
Tsapanos N, Tefas A, Nikolaidis N, Pitas I (2012) Shape matching using a binary search tree structure of weak classifiers. Pattern Recognit 45(6):2363–2376CrossRefMATH
20.
Doyon J-P, Hamel S, Chauve C (2012) An efficient method for exploring the space of gene tree/species tree reconciliations in a probabilistic framework. IEEE/ACM Trans Comput Biol Bioinform 9(1):26–39CrossRef
21.
Fang W-C, Hsu C-C, Wang C-M (2003) On the fault-tolerant embeddings of complete binary trees in the mesh interconnection networks. Inform Sci 151:51–70CrossRefMathSciNetMATH
22.
Tseng Y-C, Chen Y-S, Juang T-Y, Chang C-J (1999) Congestion-free, dilation-2 embedding of complete binary trees into star graphs. Networks 33(3):221–231CrossRefMathSciNetMATH
23.
Kumamoto M, Miyano E (2012) Optimal distortion embedding of complete binary trees into lines. Inform Process Lett 112(10):365–370CrossRefMathSciNetMATH
24.
Lin Y-B, Miller Z, Perkel M, Pritikin D, Sudborough IH (2003) Expansion of layouts of complete binary trees into grids. Discrete Appl Math 131(3):611–642CrossRefMathSciNetMATH
25.
Gupta A-K, Hambrusch S-E (1991) Embedding complete binary trees into butterfly networks. IEEE Trans Comput 40(7):853–863CrossRefMathSciNet
26.
Efe K (1991) A variation on the hypercube with lower diameter. IEEE Trans Comput 40(11):1312–1316CrossRef
27.
28.
Hilbers PAJ, Koopman MRJ, Van de Snepscheut JLA (1987) The twisted cube. In: deBakker J, Numan A, Trelearen P (eds) PARLE: Parallel Architectures and Languages Europe, 1: Parallel Architectures. Springer, Berlin, pp 152–158
29.
Wang D, Zhao L (1999) The twisted-cube connected networks. J Comput Sci Technol 14(2):181–187CrossRefMATH
30.
Fan J, Lin X (2005) The t/k-Diagnosability of the BC Graphs. IEEE Trans Comput 54(2):176–184CrossRef
31.
Vaidya AS, Rao PSN, Shankar SR (1993) A class of hypercube-like networks. In: Proceedings of the 5th IEEE symposium on parallel and distributed processing, Dallas, USA, pp 800–803
32.
Park J-H, Kim H-C, Lim H-S (2007) Panconnectivity and pancyclicity of hypercube-like interconnection networks with faulty elements. Theor Comput Sci 377(1–3):170–180CrossRefMathSciNetMATH
33.
Park J-H, Kim H-C, Lim H-S (2009) Many-to-many disjoint path covers in the presence of faulty elements. IEEE Trans Comput 58(4):528–540CrossRefMathSciNet
34.
Park J-H, Lim H-S, Kim H-C (2006) Embedding starlike trees into hypercube-like interconnection networks. In: Proceedings of the 4th international symposium on parallel and distributed processing and applications, pp 301–310
35.
36.
Choudum S-A, Usha nandini R (2004) Complete binary trees in folded and enhanced cube. Networks 43(4):266–272
37.
Kulasinghe P, Bettayeb S (1995) Embedding binary trees into crossed cubes. IEEE Trans Comput 44(7):923–929CrossRefMATH
38.
Wang X, Fan J, Jia X, Zhang S, Yu J (2011) Embedding meshes into twisted-cubes. Inform Sci 181(14):3085–3099MathSciNetMATH
39.
Wang Y, Fan J, Jia X, Huang H (2012) An algorithm to construct independent spanning trees on parity cubes. Theor Comput Sci 465(21):61–72CrossRefMathSciNetMATH
40.
Cheng B, Fan J, Jia X, Jia J (2013) Parallel construction of independent spanning trees and an application in diagnosis on Möbius cubes. J Supercomput 65(3):1279–1301CrossRef
Metadaten
Titel
Embedding complete binary trees into parity cubes
verfasst von
Zhao Liu
Jianxi Fan
Xiaohua Jia
Publikationsdatum
01.01.2015
Verlag
Springer US
Erschienen in
The Journal of Supercomputing / Ausgabe 1/2015
Print ISSN: 0920-8542
Elektronische ISSN: 1573-0484
DOI
https://doi.org/10.1007/s11227-014-1274-y

Weitere Artikel der Ausgabe 1/2015

The Journal of Supercomputing 1/2015 Zur Ausgabe

OriginalPaper

QRSF: QoS-aware resource scheduling framework in cloud computing

OriginalPaper

Subjective versus objective: classifying analytical models for productive heterogeneous performance prediction

OriginalPaper

On the computational power of WECPAR

OriginalPaper

A fast placement algorithm for embedded just-in-time reconfigurable extensible processing platform

OriginalPaper

Blue Gene/Q defragmentation for energy waste minimisation

OriginalPaper

Distributed optimization Grid resource discovery