Premium
On the Rabin number problem
Author(s) -
Duh DyiRong,
Chen GenHuey
Publication year - 1997
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(199710)30:3<219::aid-net6>3.0.co;2-o
Subject(s) - hypercube , circulant matrix , combinatorics , disjoint sets , mathematics , discrete mathematics , class (philosophy) , upper and lower bounds , node (physics) , computer science , mathematical analysis , structural engineering , artificial intelligence , engineering
Given positive integers κ and l , let R (κ, l ) denote the class of interconnection networks so that for any κ + 1 distinct nodes x , y 1 , y 2 , …, y κ there exist κ node‐disjoint paths (except at x ) of length at most l from x to y 1 , y 2 , …, y κ , respectively. The Rabin number of a network W with connectivity κ, denoted by r κ ( W ), is defined as min{ l | W ∈ R (κ, l )}. The Rabin number problem is to compute r κ ( W ) for a given network W . Computing Rabin numbers for nontrivial networks is not easy, in general. Thus far, only the Rabin number of the hypercube has been computed. In this paper, some new results on the Rabin number problem are derived. First, a theorem relating the Rabin number with both wide diameter and fault diameter is obtained. This theorem can help in the derivation of lower bounds for the Rabin numbers of circulant networks, folded hypercubes, hierarchical folded‐hypercube networks, generalized hypercubes, and WK‐recursive networks. Moreover, upper bounds are also obtained for WK‐recursive networks and a special class of generalized hypercubes. The Rabin numbers of a special class of circulant networks and a special class of generalized hypercubes are determined as a consequence of the derived upper and lower bounds. © 1997 John Wiley & Sons, Inc. Networks 30:219–230, 1997