Determination of Hamiltonian Cycles in Cube-based networks Using Generalized Gray Codes

Document Type

Article

Publication Date

5-1995

Publication Title

Computers & Electrical Engineering

Volume

21

Issue

3

First page number:

189

Last page number:

199

Abstract

Gray Codes (GCs) are useful in finding the Hamiltonian path, embedding linear and mesh graphs, and identification of operational subcubes in a cube with some already allocated regions. We generalize the conventional GCs by allowing the successive codewords to have a Hamming distance of greater than one when necessary. This generalization provides a useful methodology for solving such problems as: embedding, subnetwork allocation and deallocation, and fault tolerant routing for non-standard cube-based networks. To demonstrate the usefulness of this GC characterization, we focus on the problem of ring (or linear array) embedding into viable alternatives of the n-cube, namely, folded hypercube, incomplete hypercube, twisted hypercube and multiply-twisted hypercube. We show the power of the link label representation in identifying the Hamiltonian paths (cycles) in the cube-based networks. Using the unified link label representation, Gray Codes are derived for the aforementioned networks. The available distinct GCs for each network are further enumerated. The GCs obtained as such render Hamiltonian cycles for each cube-based topology, thus providing embedding of rings (or linear arrays) of maximum size onto the cube. It is believed that the generalized GCs introduced here can be employed to solve many other problems in networks whose connectivity is defined by the binary labels of nodes.

Keywords

Computer networks; Embedded computer systems; Gray codes; Hamiltonian systems; Hypercube networks (Computer networks)

Disciplines

Computer and Systems Architecture | Computer Engineering | Digital Communications and Networking | Electrical and Computer Engineering | VLSI and Circuits, Embedded and Hardware Systems

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