Node-disjoint paths and related problems on hierarchical cubic networks.
Journal
Networks
Journal Volume
40
Journal Issue
3
Pages
142-154
Date Issued
2002
Author(s)
Abstract
An n-dimensional hierarchical cubic network [denoted by HCN(n)] contains 2n n-dimensional hypercubes. The diameter of the HCN(n), which is equal to n + ⌊(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 by n + ⌊n/3⌋ + 4, which is nearly optimal. The (n + 1)-wide diameter and n-fault diameter of the HCN(n) are shown to be n + ⌊n/3⌋ + 3 or n + ⌊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.
Type
journal article