\(w\)-Rabin numbers and strong \(w\)-Rabin numbers of folded hypercubes. (English) Zbl 1161.05328
Summary: The \(w\)-Rabin number of a network \(W\) is the minimum \(l\) so that for any \(w+1\) distinct nodes \(s, d_{1},d_{2},\dotsc,d_w\) of W, there exist \(w\) node-disjoint paths from \(s\) to \(d_1, d_2,\dotsc, d_w\), respectively, whose maximal length is not greater than \(l\), where \(w\) is not greater than the node connectivity of \(W\). If \(\{d_{1},d_{2},\dotsc,d_w \} \) is allowed to be a multiset, then the resulting minimum \(l\) is called the strong \(w\)-Rabin number of \(W\). In this article, we show that both the \(w\)-Rabin number and the strong \(w\)-Rabin number of a \(k\)-dimensional folded hypercube are equal to \( \lceil k/2 \rceil \) for \(1\leq w \leq \lceil k/2 \rceil -1\), and \(\lceil k/2 \rceil +1 \) for \(\lceil k/2 \rceil \leq w \leq k+1\), where \( k\geq 5\). Each path obtained is shortest or second shortest. The results of this paper also solve an open problem raised by S.-C. Liaw and G.J. Chang [Discrete Math. 196, No.1-3, 219–227 (1999; Zbl 0931.68084].
MSC:
| 05C38 | Paths and cycles |
| 68M10 | Network design and communication in computer systems |
| 90B10 | Deterministic network models in operations research |
| 90C35 | Programming involving graphs or networks |
Keywords:
folded hypercube; hypercube; node-disjoint paths; optimization problem; \(w\)-Rabin number; strong \(w\)-Rabin numberCitations:
Zbl 0931.68084References:
| [1] | Extremal graph theory, Academic Press, New York, 1978. · Zbl 0419.05031 |
| [2] | and , Graph theory with applications, North-Holland, New York, 1976. · Zbl 1226.05083 · doi:10.1007/978-1-349-03521-2 |
| [3] | Cao, IEEE Trans Comput 48 pp 88– (1999) |
| [4] | Chang, J Inf Sci Eng 16 pp 291– (2000) |
| [5] | Chen, IEEE Trans Parallel Distr Syst 8 pp 1196– (1997) |
| [6] | Chen, Theory Comput Syst 37 pp 547– (2004) |
| [7] | Choudum, Networks 43 pp 266– (2004) |
| [8] | Duh, Networks 30 pp 219– (1997) |
| [9] | Duh, IEEE Trans Parallel Distr Syst 6 pp 714– (1995) |
| [10] | El-Amawy, IEEE Trans Parallel Distr Syst 2 pp 31– (1991) |
| [11] | Fu, IEEE Trans Parallel Distr Syst 16 pp 853– (2005) |
| [12] | and , Short containers in Cayley graphs, Rutgers University, 2001, New Jersey. |
| [13] | and , Fault tolerant routing in toroidal networks, Proceedings of the First Aizu International Symposium on Parallel Algorithms and Architecture Synthesis, IEEE Computer Society Press, Los Alamitos, CA, 1995, pp. 162–168. |
| [14] | Hsieh, Comput Math 53 pp 1040– (2007) |
| [15] | Hsu, Int J Mini Microcomput 16 pp 35– (1994) |
| [16] | One-to-many disjoint paths in the hypercube and folded hypercube, PhD Thesis, Department of Computer Science and Information Engineering, National Taiwan University, Taipei, Taiwan, 2001, http://mail.nkmu.edu.tw/mis/lai-phd.pdf. |
| [17] | Lai, Theor Comput Sci 341 pp 196– (2005) |
| [18] | Liaw, J Combin Optim 4 pp 371– (1999) |
| [19] | Liaw, Discrete Math 196 pp 219– (1999) |
| [20] | Rabin, J ACM 36 pp 335– (1989) |
| [21] | Saad, IEEE Trans Comput 37 pp 867– (1988) |
| [22] | Sung, IEEE Trans Parallel Distr Syst 8 pp 187– (1997) |
| [23] | Wang, J Parallel Distr Comput 61 pp 545– (2001) |
| [24] | M, Appl Math Lett 19 pp 140– (2006) |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
