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

摘要

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