Routing in Unidirectional (n,k)-star graphs
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...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
International Institute of Informatics and Cybernetics
2006-06-01
|
| Series: | Journal of Systemics, Cybernetics and Informatics |
| Subjects: | |
| Online Access: | http://www.iiisci.org/Journal/CV$/sci/pdfs/P980038.pdf
|
| Summary: | 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. |
|---|---|
| ISSN: | 1690-4524 |