Topological properties of hierarchical cubic networks

Wei Kuo Chiang, Rong-Jaye Chen*

*Corresponding author for this work

Research output: Contribution to journalArticle

12 Scopus citations

Abstract

The hierarchical cubic network (HCN), which takes hypercubes as basic clusters, was first introduced in [6]. Compared with the hypercube of the same size, the HCN requires only about half the number of links and provides a lower diameter. This paper first proposes a shortest-path routing algorithm and an optimal broadcasting algorithm for the HCN. We then show that the HCN is optimal fault tolerant by constructing node-disjoint paths between any two nodes, and demonstrate that the HCN is Hamiltonian. Moreover, it is shown that the average dilation for hypercube emulation on the HCN is bounded by 2. This result guarantees that all the algorithms designed for the hypercube can be executed on the HCN with a small degradation in time performance.

Original languageEnglish
Pages (from-to)289-307
Number of pages19
JournalJournal of Systems Architecture
Volume42
Issue number4
DOIs
StatePublished - 10 Nov 1996

Keywords

  • Broadcasting
  • Emulation
  • Fault tolerance
  • Hamiltonian
  • Hypercube
  • Interconnection network
  • Shortest-path routing

Fingerprint Dive into the research topics of 'Topological properties of hierarchical cubic networks'. Together they form a unique fingerprint.

  • Cite this