Computer Science ›› 2013, Vol. 40 ›› Issue (Z6): 265-270.

Previous Articles     Next Articles

Some New Cartesian Product Interconnection Networks

SHI Hai-zhong   

  • Online:2018-11-16 Published:2018-11-16

Abstract: Star network,pancake network,bubble sort network,modified bubble sort network,wheel network,etc,are not only Cayley graphs but also important interconnection networks.In this paper,we develop many new networks,called Cartesian product networks of the ring network,the barrell shifter network,the ILLIAC networks,the n-cube and the Star network,the pancake network,the bubble sort network,the modified bubble sort net works,the wheel network,respectively.These networks are shown to have better performance,as measured by some parameters(such as,dia-meter,etc.)than the n-cubes or the Star networks.

Key words: Cayley graph,Interconnection network,Cartesian product interconnection network,n-cube,Star network

[1] Akers S B,Harel D,Krishnamurphy B.The star graph:An attractive alternative to the n-cube[C]∥Proceedings of International Conference on Parallel Processing.1987:393-400
[2] Akers S B,Krishnamurthy B.A group-theoretic Model for symmetric interconnection networks [J].IEEE Transactions on Computers,1989,38(4):555-565
[3] 师海忠.互连网络的代数环模型[D].北京:中国科学院应用数学研究所,1998
[4] 徐俊明.组合网络理论[M].北京:科学出版社,2007
[5] Lakshmivaraha S,Two J-S,Dhall S K.Symmetry in interconnection networks based on Cayley graphs of permutation groups:a survey[J].Parallel computing,1993,19(4):361-407
[6] Andre F,Verjus J P.Hypercubes and Distributed computer[M].Amsterdam,New York,Oxford:North-Halland,1989
[7] Biggs N.Algebraic Graph Theory [M].Cambridge:CambridgeUniversity Press,1993 (下转第306页)(上接第270页)
[8] Bondy J A,Murty U S R.Graph Theory with Applications[M].London and Basingstoke:MacMillan Press LTD,1976
[9] Harary F.Recent results and unsolved problems on hypercube theory[M]. Alavi Y ,Chartrand G,Oellermann O R,et al.,eds.Graph Theory,Combinatorics,Applications,John Wiley & sons,1991:621-632
[10] Barnes G H,Brown R M,Kato M,et al.The ILLIAN computer [J].IEEE Transactions on Computers,1968,17:746-757
[11] Kai Hwang.高等计算机系统结构:并行性、可扩展性、可编程性[M].王鼎兴,等译.北京:清华大学出版社,南宁:广西科学技术出版社,1995
[12] 李亚民.计算机组成与系统结构[M].北京:清华大学出版社,2000
[13] Witte D,Gallian J A.A survey Hamilton cycles in Cayley graphs [J].Discrete Mathematics 1984,51:293-304
[14] Curran S J,Gallian J A.Perspectives Hamiltonian cycles and paths in Cayley graphs and digraphs-A survey[J].Discrete Mathematic,1996,156:1-18
[15] Alspach B,Bermond J C,Sotteau D.Decompositions into Cycle:Hamilton decompositions[M].Hahn G,ed.Cycles and Rays(kluwer Academic pubbishers,Netherlands),1990:9-18
[16] Araki T,Kikuchi Y.Hamiltonian laceability of bubble sortgraphs with edge faults[J].Information Sciences,2007,177:2679-2691
[17] 师海忠,路建波.关于互连网络的几个猜想[J].计算机工程与应用,2008,44(31):112-115
[18] 高随祥.图论与网络流理论[M].北京:高等教育出版社,2009

No related articles found!
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!