Node‐disjoint paths and related problems on hierarchical cubic networks
Jung‐Sheng Fu, Gen-Huey Chen, Dyi‐Rong Duh · Networks · 2002
Abstract Ann‐dimensional hierarchical cubic network [denoted by HCN(n)] contains 2nn‐dimensional hypercubes. The diameter of the HCN(n), which is equal ton+ ⌊(n+ 1)/3⌋ + 1, is about two‐thirds the diameter of a comparable hypercube, even though it uses about half as many links per node. In this paper, a maximal number of node‐disjoint paths are constructed between every two distinct nodes of the HCN(n). Their maximal length is bounded above byn+ ⌊n/3⌋ + 4, which is nearly optimal. The (n+ 1)‐wide diameter andn‐fault diameter of the HCN(n) are shown to ben+ ⌊n/3⌋ + 3 orn+ ⌊n/3⌋ + 4, which are about two‐thirds those of a comparable hypercube. Our results reveal that the HCN(n) has a smaller wide diameter and fault diameter than those of a comparable hypercube. © 2002 Wiley Periodicals, Inc.