On Embedding Rings into a Star-related network

Document Type

Article

Publication Date

6-1997

Publication Title

Information Sciences

Volume

99

Issue

1-2

First page number:

21

Last page number:

35

Abstract

It is shown that, in the star graph, it is always possible to form a Hamiltonian path between two nodes as long as the distance between them is odd. This result leads to the proof of Hamiltonicity for the clustered-star graph. The results can readily be used in optimal embedding of a linear array of processors (or a ring) in the star graph. The embedding problem is also solved when one or more processors are faulty in the network. The length of the linear array and the ring in this case is shown to be (n!−m!) where m is the dimension of the smallest star graph which contains all the faulty processors.

Keywords

Array processors; Cayley graphs; Computer algorithms; Hamiltonian graph theory; Hypercube networks (Computer networks); Parallel computers; Routing (Computer network management)

Disciplines

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

Language

English

Permissions

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

Share

COinS