標題: Topological properties of hierarchical cubic networks
作者: Chiang, WK
Chen, RJ
資訊工程學系
Department of Computer Science
關鍵字: hypercube;interconnection network;shortest-path routing;broadcasting;fault tolerance;Hamiltonian;emulation
公開日期: 10-十一月-1996
摘要: 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.
URI: http://dx.doi.org/10.1016/1383-7621(96)00019-7
http://hdl.handle.net/11536/928
ISSN: 1383-7621
DOI: 10.1016/1383-7621(96)00019-7
期刊: JOURNAL OF SYSTEMS ARCHITECTURE
Volume: 42
Issue: 4
起始頁: 289
結束頁: 307
顯示於類別:期刊論文


文件中的檔案:

  1. A1996VT40600004.pdf