Unidirectional star graphs

Khaled Day*, Anand Tripathi

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

33 Citations (Scopus)


We propose an assignment of directions to the edges of the n-star graph and derive attractive properties for the resulting unidirectional star graph USn. A simple polarity function is used to define the directions of the edges. USn is shown to be strongly connected and recursively structured. The number of incoming ports of a node in USn is equal to the number of its outgoing ports (plus or minus one when n is even). The polarities of the ports of a neighboring node can be directly obtained from the polarities of the ports of the local node. These properties have allowed the design of a near optimal distributed routing algorithm as indicated by simulation results on all USn graphs with up to 362,880 nodes.

Original languageEnglish
Pages (from-to)123-129
Number of pages7
JournalInformation Processing Letters
Issue number3
Publication statusPublished - Mar 8 1993
Externally publishedYes


  • Combinatorial problems
  • directed graphs
  • distributed computing
  • distributed routing
  • interconnection networks
  • star graphs

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Signal Processing
  • Information Systems
  • Computer Science Applications


Dive into the research topics of 'Unidirectional star graphs'. Together they form a unique fingerprint.

Cite this