Title :
Bubblesort star graphs: a new interconnection network
Author :
Chou, Zi-Tsan ; Hsu, Chiun-Chieh ; Sheu, Jang-Ping
Author_Institution :
Dept. of Comput. Sci. & Inf. Eng., Nat. Central Univ., Chung-Li, Taiwan
Abstract :
In this paper, we propose and analyze a new interconnection network called bubblesort star graph, which is the merger of the bubblesort graph and the star graph. We present the deadlock-free wormhole routing algorithm for the proposed network. We also develop the method to embed a mesh into a bubblesort star graph with dilation two and expansion one. Besides, we use the recursive scheme to embed the multiple disjoint copies of the hypercube into a bubblesort star graph with all faults recovery capacity as well as constant expansion and dilation one or two. This reflects the fact that the embeddability of the bubblesort star graph is much better than that of the star graph
Keywords :
graph theory; multiprocessor interconnection networks; network routing; bubblesort star graphs; deadlock-free wormhole routing algorithm; dilation two; expansion one; hypercube; interconnection network; mesh; multiple disjoint copies; Binary trees; Computer science; Corporate acquisitions; Electronic mail; Hypercubes; Information management; Multiprocessor interconnection networks; Network topology; Routing; System recovery;
Conference_Titel :
Parallel and Distributed Systems, 1996. Proceedings., 1996 International Conference on
Conference_Location :
Tokyo
Print_ISBN :
0-8186-7267-6
DOI :
10.1109/ICPADS.1996.517543
