Routing in Unidirectional (n,k)-star graphs

Abstract

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.

Keywords

• graphs
• routing
• distributed
• Networks
• star
• Interconnection