%0 Conference Proceedings
%T Embedding Algorithms for Bubble-Sort, Macro-Star, and Transposition Graphs
%+ Department of Computer Education & Engineering
%+ Research & Development Team, Jeonnam Technopark
%+ Department of Computer Science Education
%A Lee, Hyeongok
%A Kim, Dongwan
%A Seo, Junghyun
%A Kim, Mihye
%< avec comité de lecture
%( Lecture Notes in Computer Science
%B IFIP International Conference on Network and Parallel Computing (NPC)
%C Zhengzhou, China
%Y Chen Ding; Zhiyuan Shao; Ran Zheng
%I Springer
%3 Network and Parallel Computing
%V LNCS-6289
%P 134-143
%8 2010-09-13
%D 2010
%R 10.1007/978-3-642-15672-4_12
%K Interconnection network
%K Embedding
%K Dilation
%Z Computer Science [cs]/Digital Libraries [cs.DL]Conference papers
%X 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.
%G English
%2 https://inria.hal.science/hal-01054983/document
%2 https://inria.hal.science/hal-01054983/file/NPC10-1569315047-manucript.pdf
%L hal-01054983
%U https://inria.hal.science/hal-01054983
%~ IFIP-LNCS
%~ IFIP
%~ IFIP-LNCS-6289
%~ IFIP-NPC
%~ IFIP-2010