Premium
On container length and connectivity in unidirectional hypercubes
Author(s) -
Jwo JungSing,
Tuan TaiChing
Publication year - 1998
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/(sici)1097-0037(199812)32:4<307::aid-net7>3.0.co;2-5
Subject(s) - hypercube , combinatorics , vertex (graph theory) , shortest path problem , path length , disjoint sets , mathematics , discrete mathematics , computer science , graph , computer network
In this paper, we show that the two unidirectional binary n ‐cubes, namely, Q 1 ( n ) and Q 2 ( n ), proposed as high‐speed networking schemes by Chou and Du are maximum fault‐tolerant, that is, from vertex a to vertex b in the network, we can determine a set of ζ( a, b ) vertex‐disjoint routing paths, where ζ( a, b ) = ⌈ n /2⌉, if a has even parity and b has odd parity and ⌊ n /2⌋ otherwise. Furthermore, the container problem as defined by Hsu for the two maximum fault‐tolerant, unidirectional topologies is studied. In particular, we show that the smallest possible length for any maximum fault‐tolerant container from a to b is at most (1) ℓ + 4, where ℓ is the shortest path length in Q 1 ( n ) from a to b , and (2) ℓ + 5, where ℓ is the shortest path length in Q 2 ( n ) ( n is odd) (i) from a to b when a and b have the same leading‐bit values and (ii) from a to b ′ ( b ′ and b only differ at leading‐bit positions) when otherwise. © 1998 John Wiley & Sons, Inc. Networks 32: 307–317, 1998