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

Abstract : 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.
Type de document :
Communication dans un congrès
Chen Ding; Zhiyuan Shao; Ran Zheng. IFIP International Conference on Network and Parallel Computing (NPC), Sep 2010, Zhengzhou, China. Springer, Lecture Notes in Computer Science, LNCS-6289, pp.134-143, 2010, Network and Parallel Computing. 〈10.1007/978-3-642-15672-4_12〉
Liste complète des métadonnées

Littérature citée [11 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01054983
Contributeur : Hal Ifip <>
Soumis le : lundi 11 août 2014 - 09:05:30
Dernière modification le : vendredi 11 août 2017 - 17:43:54
Document(s) archivé(s) le : mercredi 26 novembre 2014 - 21:40:26

Fichier

NPC10-1569315047-manucript.pdf
Fichiers produits par l'(les) auteur(s)

Licence


Distributed under a Creative Commons Paternité 4.0 International License

Identifiants

Citation

Hyeongok Lee, Dongwan Kim, Junghyun Seo, Mihye Kim. Embedding Algorithms for Bubble-Sort, Macro-Star, and Transposition Graphs. Chen Ding; Zhiyuan Shao; Ran Zheng. IFIP International Conference on Network and Parallel Computing (NPC), Sep 2010, Zhengzhou, China. Springer, Lecture Notes in Computer Science, LNCS-6289, pp.134-143, 2010, Network and Parallel Computing. 〈10.1007/978-3-642-15672-4_12〉. 〈hal-01054983〉

Partager

Métriques

Consultations de la notice

73

Téléchargements de fichiers

119