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
|
| _version_ | 1819267286198910976 |
|---|---|
| author | Eddie Cheng Serge Kruk |
| author_facet | Eddie Cheng Serge Kruk |
| author_sort | Eddie Cheng |
| collection | DOAJ |
| description | 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. |
| first_indexed | 2024-12-23T21:14:45Z |
| format | Article |
| id | doaj.art-1f909801392848a89a3f9b2b1cf26cef |
| institution | Directory Open Access Journal |
| issn | 1690-4524 |
| language | English |
| last_indexed | 2024-12-23T21:14:45Z |
| publishDate | 2006-06-01 |
| publisher | International Institute of Informatics and Cybernetics |
| record_format | Article |
| series | Journal of Systemics, Cybernetics and Informatics |
| spelling | doaj.art-1f909801392848a89a3f9b2b1cf26cef2022-12-21T17:30:57ZengInternational Institute of Informatics and CyberneticsJournal of Systemics, Cybernetics and Informatics1690-45242006-06-01437478Routing in Unidirectional (n,k)-star graphsEddie Cheng0Serge Kruk1 Oakland University Oakland University 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.http://www.iiisci.org/Journal/CV$/sci/pdfs/P980038.pdf graphsroutingdistributedNetworksstarInterconnection |
| spellingShingle | Eddie Cheng Serge Kruk Routing in Unidirectional (n,k)-star graphs Journal of Systemics, Cybernetics and Informatics graphs routing distributed Networks star Interconnection |
| title | Routing in Unidirectional (n,k)-star graphs |
| title_full | Routing in Unidirectional (n,k)-star graphs |
| title_fullStr | Routing in Unidirectional (n,k)-star graphs |
| title_full_unstemmed | Routing in Unidirectional (n,k)-star graphs |
| title_short | Routing in Unidirectional (n,k)-star graphs |
| title_sort | routing in unidirectional n k star graphs |
| topic | graphs routing distributed Networks star Interconnection |
| url | http://www.iiisci.org/Journal/CV$/sci/pdfs/P980038.pdf
|
| work_keys_str_mv | AT eddiecheng routinginunidirectionalnkstargraphs AT sergekruk routinginunidirectionalnkstargraphs |