A depth-first search routing algorithm for star graphs and its performance evaluation (Q1328866)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | A depth-first search routing algorithm for star graphs and its performance evaluation |
scientific article |
Statements
A depth-first search routing algorithm for star graphs and its performance evaluation (English)
0 references
8 August 1994
0 references
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.
0 references
star graph interconnection network
0 references
fault-tolerant routing algorithm
0 references