Characterization of Parallel Paths in Arrangement Graphs
Khaled Day, Anand Tripathi · 1998
In this paper we fully characterize node-disjoint (parallel) paths in arrangement graph interconnection networks which have been presented as generalized star graphs for interconnecting large multiprocessor systems. We characterize complete families of parallel paths between any two nodes of an arrangement graph. The length of each path is at most four plus the minimum distance between the two nodes. 1. INTRODUCTION The arrangement graph has been proposed (Day & Tripathi 1992) as an attractive interconnection topology for large multiprocessor systems. An arrangement graph, A n,k , of parameters n and k, is regular, has degree k(n-k), has n! (n-k)! vertices, and has diameter ë 3 2 kû. A n,k is vertex and edge symmetric, recursively structured, has a simple and optimal distributed routing algorithm, and many fault tolerance properties. This topology has been presented as a generalization of the star graph (Akers et al. 1986, 1987). The star graph topology has drawn a lot of attention...