星图应用哈米尔顿拉丁方的并行路由算法

广东工业大学学报 ›› 2011, Vol. 28 ›› Issue (1): 62-67.

星图应用哈米尔顿拉丁方的并行路由算法

广东工业大学应用数学学院,广东广州 510006

出版日期:2011-12-25 发布日期:2011-12-25
作者简介:王丹丹(1984-),女,硕士研究生,主要研究方向为图论.

A Parallel Routing Algorithm on Star Graph Network Employing the Hamiltonian Circuit Latin Square

Faculty of Applied Mathematics,Guangdong University of Technology,Guangzhou 510006,China

Online:2011-12-25 Published:2011-12-25

摘要/Abstract

摘要： 提出了一种星图的信息路由算法.在星图中,从一个源节点到一个目的节点传递k个数据包,令第i个数据包将沿着第i条路径传输(1≤i≤k).对所有的数据包,要保证每个数据包的路径与其余数据包的路径不相交.为了构造这样的路由,提出了应用哈米尔顿循环拉丁方的星图信息路由算法,并给出该算法的时间复杂度是O(n2).

关键词: 并行算法;星图网络;哈米尔顿拉丁方;最短路径

Abstract: An algorithm for constructing the routing of a message on the star graph is proposed.The k packets are transmitted from a source node to a destination node simultaneously along paths on the star graph network,where the ith packet traverses along the ith path (1≤i≤k).In order for all packets to arrive at the destination node quickly and securely,the ith path must be nodedisjoint from all other paths.For the construction of these paths,the Hamiltonian circuit latin square (HCLS) is employed in this algorithm,which has O(n2)of the time complexity.

Key words: parallel routing algorithm; star graph network; Hamiltonian circuit latin square; the shortest path

王丹丹, 郭大昌, 王静. 星图应用哈米尔顿拉丁方的并行路由算法[J]. 广东工业大学学报, 2011, 28(1): 62-67.

WANG Dan-Dan, GUO Da-Chang, WANG Jing. A Parallel Routing Algorithm on Star Graph Network Employing the Hamiltonian Circuit Latin Square[J]. Journal of Guangdong University of Technology, 2011, 28(1): 62-67.

参考文献

［1］ Day Khaled,Tripathi Anand.A Comparative Study of Topological Properties of Hypercubes and Star Graphs［J］.IEEE Transactions on Parallel and Distributed Systems,1994,5(1):31-38.

［2］ Chen ChiChang,Chen Jianer.VertexDisjoint Routings in Star Graphs［J］.IEEE Algorithms and Architectures for Parallel Processing,1995,1(1921):460-464.

［3］徐俊明.组合网络［M］.北京：科学出版社,2007.

［4］唐高华.近世代数［M］.北京：清华大学出版社,2008.

［5］ Yeh ShengI,Yang ChangBiau,Chen HonChan.FaultTolerant Routing on the Star Graph with Safety Vectors［J］.IEEE Parallel Architectures,Algorithms and Networks,2002 (5):266-271.

［6］Cho Youngjoo,Chung Ilyong.A parallel routing algorithm on circulant neworks employing the Hamiltion circution latins quaer［J］.Information Sciences,2006,176(21):3132-2142.

［7］Choi Dongmin,Chung Ilyong.A parallel routing algorithm on recursive cube of rings neworks employing the Hamiltion circution latins quaer［J］.Information Sciences,2008,178(6):1533-1541.

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed