Routing in Unidirectional (n,k)-star graphs
Eddie Cheng, Serge Kruk
The class of (n,k)-star graphs and their unidirectional version
were introduced as generalizations of star graphs and unidirectional
star graphs respectively. In this paper, we substantially improved
previously known bound for the the diameter of unidirectional
(n,k)-star graphs. The previous bound was 10k-5 for small k
and 5k+5[(n-1)/2] for large k; the new bound is
7(k-3)+18.
In addition, a distributing routing algorithm is presented, analyzed
theoretically for worst-case behaviour and exercised experimentally
for average case behaviour. Full Text
|