Fault-tolerant Embedding of Linear Arrays and Rings in the Star Graph

Authors

Shahram Latifi, University of Nevada, Las VegasFollow
Nader Bagherzadeh, University of California, IrvineFollow
R. R. Gajjala, University of Nevada, Las VegasFollow

Document Type

Article

Publication Date

3-1997

Publication Title

Computers & Electrical Engineering

Volume

23

Issue

2

First page number:

95

Last page number:

107

Abstract

Methods are presented to embed Hamiltonian paths (H-paths) and Hamiltonian cycles (H-cycles) in a star graph Sn in a faulty environment. The models considered include single-processor failure, double-process failure, and multiple-processor failures. All three models are applied to an H-path/cycle, which is formed by visiting all the (n!/4!)S₄s in an S_n in a particular order. An optimal embedding is obtained in the case of single-processor failure, wherein the length of the H-path/cycle is shown to be (n! − 2). The multiple-processor failure model is developed based on single and double processor failure models. In this case the length of the H-cycle that can be embedded is shown to be (n! − 2f), where f ≤ n − 2 is the number of faults. Another case of multiple-failure scenario is investigated by assuming that all faults are contained in a single S_m, m<n. The network in this case, is shown to reduce to a cluster-star graph. It is proven that it is always possible to formulate an H-cycle of length (n! − m!) in such a network.

Keywords

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

Disciplines

Computer and Systems Architecture | Computer Engineering | 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.

Repository Citation

Latifi, S., Bagherzadeh, N., Gajjala, R. R. (1997). Fault-tolerant Embedding of Linear Arrays and Rings in the Star Graph. Computers & Electrical Engineering, 23(2), 95-107.