Journal of South China University of Technology (Natural Science Edition) ›› 2011, Vol. 39 ›› Issue (2): 153-158.doi: 10.3969/j.issn.1000-565X.2011.02.026

• Electronics, Communication & Automation Technology • Previous Articles    

A New Type of Cayley Graph Model for Interconnection Networks Based on Wreath Product

Zhang Zhen1  Xiao Wen-jun1  Wang Xiao-ming2   

  1. 1. The south China university of technology, computer science and engineering college, guangdong guangzhou 510006; 2. Jinan university computer science, guangdong guangzhou 510632
  • Received:2010-02-09 Revised:2010-10-10 Online:2011-02-25 Published:2011-01-02
  • Contact: 张震(1975-)，男，在职博士生，暨南大学讲师，主要从事互联网络、并行分布式处理系统研究 E-mail:zhang2003174@yahoo.com.cn
  • About author:张震(1975-)，男，在职博士生，暨南大学讲师，主要从事互联网络、并行分布式处理系统研究
  • Supported by:

    国家自然科学基金资助项目(60773083)；广东省科技厅基金资助项目(8151063201000022)；暨南大学中央高校基本科研业务费专项资金资助项目(1 1610307)

PDF

909

Abstract:

Proposed in this paper is a new type of Cayley graph model for building large-scale interconnection networks,namely WG2mn,whose node degree is m＋3 when n≥3 and is m＋2 when n=2.A routing algorithm for the proposed model is also presented,and the upper bound of the algorithm diameter is deduced as 5n/2」.Moreover,the embedding properties of the model are analyzed.It is found that WG2mn is superior to other network models because it helps to construct large-scale interconnection networks with lower cost.

Key words: interconnection networks, Cayley graph, routing algorithm, network diameter, embeddability