Task allocation in the star graph

Document Type



The star graph has been known as an attractive candidate for interconnecting a large number of processors. The hierarchy of the star graph allows the assignment of its special subgraphs (substars), which have the same topological features as the original graph, to a sequence of incoming tasks. The paper proposes a new code, called star code (SC), to recognize available substars of the required size in the star graph. It is shown that task allocation based on the SC is statically optimal. The recognition ability of a given SC or a class of SC's is derived. The optimal number of SC's required for the complete substar recognition in an n-dimensional star is shown to be 2n-2.


Cayley graphs; Computer network resources; Graph theory; Parallel algorithms; Parallel processing (Electronic computers); Resource allocation--Data processing


Computer and Systems Architecture | Digital Communications and Networking | Electrical and Computer Engineering | Systems and Communications


Use Find in Your Library, contact the author, or interlibrary loan to garner a copy of the item. Publisher policy does not allow archiving the final published version. If a post-print (author's peer-reviewed manuscript) is allowed and available, or publisher policy changes, the item will be deposited.

UNLV article access

Search your library