| HAL-Inria | Publications, software ... of Inria's scientists |
Conference papers
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.
Cited literature [11 references]
https://hal.inria.fr/hal-01054983
Contributor : Hal Ifip <>
Submitted on : Monday, August 11, 2014 - 9:05:30 AM
Last modification on : Friday, August 11, 2017 - 5:43:54 PM
Long-term archiving on: : Wednesday, November 26, 2014 - 9:40:26 PM
Contributor : Hal Ifip <>
Submitted on : Monday, August 11, 2014 - 9:05:30 AM
Last modification on : Friday, August 11, 2017 - 5:43:54 PM
Long-term archiving on: : Wednesday, November 26, 2014 - 9:40:26 PM
File
NPC10-1569315047-manucript.pdf
Files produced by the author(s)
Licence
Distributed under a Creative Commons Attribution 4.0 International License