| 星图应用哈米尔顿拉丁方的并行路由算法 |
| |
| 引用本文： | 王丹丹,郭大昌,王静.星图应用哈米尔顿拉丁方的并行路由算法[J].广东工业大学学报,2011,28(1):62-67. |
| |
| 作者姓名： | 王丹丹 郭大昌 王静 |
| |
| 作者单位： | 广东工业大学,应用数学学院,广东,广州,510006 |
| |
| 摘 要： | 提出了一种星图的信息路由算法.在星图中,从一个源节点到一个目的节点传递k个数据包,令第i个数据包将沿着第i条路径传输(1≤i≤k).对所有的数据包,要保证每个数据包的路径与其余数据包的路径不相交.为了构造这样的路由,提出了应用哈米尔顿循环拉丁方的星图信息路由算法,并给出该算法的时间复杂度是O(n2).
|
| 关 键 词： | 并行算法 星图网络 哈米尔顿拉丁方 最短路径 |
A Parallel Routing Algorithm on Star Graph Network Employing the Hamiltonian Circuit Latin Square |
| |
| 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. |
| |
| Authors: | Wang Dan-dan Guo Da-chang Wang Jing |
| |
| Affiliation: | Wang Dan-dan,Guo Da-chang,Wang Jing(Faculty of Applied Mathematics,Guangdong University of Technology,Guangzhou 510006,China) |
| |
| 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. |
| |
| Keywords: | parallel routing algorithm star graph network Hamiltonian circuit latin square the shortest path |
| 本文献已被 CNKI 万方数据 等数据库收录！ |
|
