AN ALGORITHM FOR FINDING DISJOINT PATHS IN THE ALTERNATING GROUP GRAPH

摘要

For the purpose of large scale computing, we are interested in linking computers into large interconnection networks. In order for these networks to be useful, the underlying graph must possess desirable properties such as a large number of vertices, high connectivity and small diameter. In this paper, we are interested in the alternating group graph, as an interconnection network, and the k-Disjoint Path Problem. In 2005, Cheng, Kikas and Kruk showed that the alternating group graph, AG_n has the (n - 2)-Disjoint Path Property. However, their proof was an existence proof only. They did not show how to actually construct the (n - 2) disjoint paths. In this paper we develop an algebraic algorithm that constructs the (n-2) disjoint paths from scratch. We close with remarks on possible research directions stemming from this work.