Operations Research Transactions

• Original Articles • Previous Articles     Next Articles

A vector graph model for interconnection networks

 SHI  Hai-Zhong, NIU  Pan-Feng, MA  Ji-Yong, HOU  Fei-Fei   

  • Received:2011-04-28 Revised:2011-07-12 Online:2011-09-20 Published:2011-09-29

Abstract: the n-cube, the ring network, the k-ary-n-cube, the star network, the pancake network, the bubble sort network, the Cayley graph of transposition tree, the De Bruijn network, the Kautz network, the consecutive-d digraph, the ILLIAC network, the circulant digraph, the circulant undirected graph, the ring digraph, etc have been widely used as processor/communication networks. The performance of such networks is often measured through an analysis of their degree, diameter, connectivity, fault tolerance, routing algorithm, etc. In this paper, at first, we proposed the concepts --- vector digraph and vector graph. Second, we developed vector digraph model and vector graph model for interconnection networks for designing, analyzing, and improving above networks. Furthermore, we shew that the networkd mentioned above can be concisely represented in the two models. More importantly, we shew that the two models enabled us to design new networks --- double star network and triangle network based on vector graphs.

Key words:  interconnection network, vector digraph, vector graph, double star network, triangle
network