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

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

作　　者：王丹丹[1] 郭大昌[1] 王静[1] 

机构地区：[1]广东工业大学应用数学学院,广东广州510006

出　　处：《广东工业大学学报》2011年第1期62-67,共6页Journal of Guangdong University of Technology

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

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

分 类 号：O157.5[理学—数学]