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