https://scholars.lib.ntu.edu.tw/handle/123456789/61228
標題: | Strong Rabin numbers of folded hypercubes | 作者: | Lai, Cheng-Nan Chen, Gen Huey |
關鍵字: | Folded hypercube;Hypercube;Node-disjoint paths;Optimization problem;Strong Rabin number | 公開日期: | 2005 | 出版社: | Taipei:National Taiwan University Dept Chem Engn | 起(迄)頁: | - | 來源出版物: | Theoretical Computer Science | 摘要: | The strong Rabin number of a network W of connectivity k is the minimum l so that for any k +1 nodes s, d1, d2, . . . , dk of W, there exist k node-disjoint paths from s to d1, d2, . . . , dk, respectively, whose maximal length is not greater than l, where s /â {d1, d2, . . . , dk} and d1, d2, . . . , dk are not necessarily distinct. In this paper, we show that the strong Rabin number of a k-dimensional folded hypercube is k/2 + 1, where k/2 is the diameter of the k-dimensional folded hypercube. Each node-disjoint path we obtain has length not greater than the distance between the two end nodes plus two. This paper solves an open problem raised by Liaw and Chang. |
URI: | https://www.scopus.com/inward/record.uri?eid=2-s2.0-23844513092&doi=10.1016%2fj.tcs.2005.02.010&partnerID=40&md5=7d1e45e43af43f91c203b2d0e6cf4e1c | 其他識別: | 246246/2006111501244229 | DOI: | 10.1016/j.tcs.2005.02.010 |
顯示於: | 化學工程學系 |
在 IR 系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。