Embedding Algorithms for Bubble-Sort, Macro-Star, and Transposition Graphs - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Communication Dans Un Congrès Année : 2010

Embedding Algorithms for Bubble-Sort, Macro-Star, and Transposition Graphs

Résumé

Bubble-sort, macro-star, and transposition graphs are interconnection networks with the advantages of star graphs in terms of improving the network cost of a hypercube. These graphs contain a star graph as their sub-graph, and have node symmetry, maximum fault tolerance, and recursive partition properties. This study proposes embedding methods for these graphs based on graph definitions, and shows that a bubble-sort graph Bn can be embedded in a transposition graph Tn with dilation 1 and expansion 1. In contrast, a macro-star graph MS(2, n) can be embedded in a transposition graph with dilation n, but with an average dilation of 2 or under.
Fichier principal
Vignette du fichier
NPC10-1569315047-manucript.pdf (215.79 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-01054983 , version 1 (11-08-2014)

Licence

Paternité

Identifiants

Citer

Hyeongok Lee, Dongwan Kim, Junghyun Seo, Mihye Kim. Embedding Algorithms for Bubble-Sort, Macro-Star, and Transposition Graphs. IFIP International Conference on Network and Parallel Computing (NPC), Sep 2010, Zhengzhou, China. pp.134-143, ⟨10.1007/978-3-642-15672-4_12⟩. ⟨hal-01054983⟩
89 Consultations
130 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More