On embedding Hamiltonian cycles in crossed cubes

Research output: Contribution to journalArticle

29 Citations (Scopus)

Abstract

We study the embedding of Hamiltonian cycle in the Crossed Cube, a prominent variant of the classical hypercube, which is obtained by crossing some straight links of a hypercube, and has been attracting much research interest in literatures since its proposal. We will show that due to the loss of link-topology regularity, generating Hamiltonian cycles in a crossed cube is a more complicated procedure than in its original counterpart. The paper studies how the crossed links affect an otherwise succinct process to generate a host of well-structured Hamiltonian cycles traversing all nodes. The condition for generating these Hamiltonian cycles in a crossed cube is proposed. An algorithm is presented that works out a Hamiltonian cycle for a given link permutation. The useful properties revealed and algorithm proposed in this paper can find their way when system designers evaluate a candidate network' s competence and suitability, balancing regularity and other performance criteria, in choosing an interconnection network.

Original languageEnglish
Pages (from-to)334-346
Number of pages13
JournalIEEE Transactions on Parallel and Distributed Systems
Volume19
Issue number3
DOIs
StatePublished - 1 Mar 2008

Fingerprint

Hamiltonians
Topology

Keywords

  • Crossed cube
  • Embedding
  • Hamiltonian cycles
  • Interconnection architectures
  • Network topology

Cite this

@article{735a015ea5bb4ed4a85367b387327dcc,
title = "On embedding Hamiltonian cycles in crossed cubes",
abstract = "We study the embedding of Hamiltonian cycle in the Crossed Cube, a prominent variant of the classical hypercube, which is obtained by crossing some straight links of a hypercube, and has been attracting much research interest in literatures since its proposal. We will show that due to the loss of link-topology regularity, generating Hamiltonian cycles in a crossed cube is a more complicated procedure than in its original counterpart. The paper studies how the crossed links affect an otherwise succinct process to generate a host of well-structured Hamiltonian cycles traversing all nodes. The condition for generating these Hamiltonian cycles in a crossed cube is proposed. An algorithm is presented that works out a Hamiltonian cycle for a given link permutation. The useful properties revealed and algorithm proposed in this paper can find their way when system designers evaluate a candidate network' s competence and suitability, balancing regularity and other performance criteria, in choosing an interconnection network.",
keywords = "Crossed cube, Embedding, Hamiltonian cycles, Interconnection architectures, Network topology",
author = "Dajin Wang",
year = "2008",
month = "3",
day = "1",
doi = "10.1109/TPDS.2007.70729",
language = "English",
volume = "19",
pages = "334--346",
journal = "IEEE Transactions on Parallel and Distributed Systems",
issn = "1045-9219",
publisher = "IEEE Computer Society",
number = "3",

}

On embedding Hamiltonian cycles in crossed cubes. / Wang, Dajin.

In: IEEE Transactions on Parallel and Distributed Systems, Vol. 19, No. 3, 01.03.2008, p. 334-346.

Research output: Contribution to journalArticle

TY - JOUR

T1 - On embedding Hamiltonian cycles in crossed cubes

AU - Wang, Dajin

PY - 2008/3/1

Y1 - 2008/3/1

N2 - We study the embedding of Hamiltonian cycle in the Crossed Cube, a prominent variant of the classical hypercube, which is obtained by crossing some straight links of a hypercube, and has been attracting much research interest in literatures since its proposal. We will show that due to the loss of link-topology regularity, generating Hamiltonian cycles in a crossed cube is a more complicated procedure than in its original counterpart. The paper studies how the crossed links affect an otherwise succinct process to generate a host of well-structured Hamiltonian cycles traversing all nodes. The condition for generating these Hamiltonian cycles in a crossed cube is proposed. An algorithm is presented that works out a Hamiltonian cycle for a given link permutation. The useful properties revealed and algorithm proposed in this paper can find their way when system designers evaluate a candidate network' s competence and suitability, balancing regularity and other performance criteria, in choosing an interconnection network.

AB - We study the embedding of Hamiltonian cycle in the Crossed Cube, a prominent variant of the classical hypercube, which is obtained by crossing some straight links of a hypercube, and has been attracting much research interest in literatures since its proposal. We will show that due to the loss of link-topology regularity, generating Hamiltonian cycles in a crossed cube is a more complicated procedure than in its original counterpart. The paper studies how the crossed links affect an otherwise succinct process to generate a host of well-structured Hamiltonian cycles traversing all nodes. The condition for generating these Hamiltonian cycles in a crossed cube is proposed. An algorithm is presented that works out a Hamiltonian cycle for a given link permutation. The useful properties revealed and algorithm proposed in this paper can find their way when system designers evaluate a candidate network' s competence and suitability, balancing regularity and other performance criteria, in choosing an interconnection network.

KW - Crossed cube

KW - Embedding

KW - Hamiltonian cycles

KW - Interconnection architectures

KW - Network topology

UR - http://www.scopus.com/inward/record.url?scp=40449138262&partnerID=8YFLogxK

U2 - 10.1109/TPDS.2007.70729

DO - 10.1109/TPDS.2007.70729

M3 - Article

AN - SCOPUS:40449138262

VL - 19

SP - 334

EP - 346

JO - IEEE Transactions on Parallel and Distributed Systems

JF - IEEE Transactions on Parallel and Distributed Systems

SN - 1045-9219

IS - 3

ER -