A depth-first search routing algorithm for star graphs and its performance evaluation (Q1328866)

The star graph interconnection network of order \(n\) has \(n!\) vertices in correspondence with \(n!\) permutations of \(n\) letters. Two vertices are adjacent if they disagree in the first position and in precisely one other position (for example \(abcd\) and \(cbad\) are adjacent, while \(abcd\) and \(adcb\) are not). A fault-tolerant routing algorithm is developed for this network, and probabilities are calculated that the algorithm succeeds in finding an optimal path. The method always finds a path when one exists.