Premium
Node‐disjoint paths and related problems on hierarchical cubic networks
Author(s) -
Fu JungSheng,
Chen GenHuey,
Duh DyiRong
Publication year - 2002
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.10040
Subject(s) - hypercube , combinatorics , disjoint sets , node (physics) , bounded function , mathematics , discrete mathematics , computer science , physics , mathematical analysis , quantum mechanics
An n ‐dimensional hierarchical cubic network [denoted by HCN( n )] contains 2 n 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.