The k-ary n-cube Qkn （n ≥2 and k ≥3） is one of the most popular interconnection networks. In this paper, we consider the problem of a fault- free Hamiltonian cycle passing through a prescribed linear forest （i.e....The k-ary n-cube Qkn （n ≥2 and k ≥3） is one of the most popular interconnection networks. In this paper, we consider the problem of a fault- free Hamiltonian cycle passing through a prescribed linear forest （i.e., pairwise vertex-disjoint paths） in the 3-ary n-cube Qn^3 with faulty edges. The following result is obtained. Let E0 （≠θ） be a linear forest and F （≠θ） be a set of faulty edges in Q3 such that E0∩ F = 0 and ｜E0｜ ＋｜F｜ ≤ 2n - 2. Then all edges of E0 lie on a Hamiltonian cycle in Qn^3- F, and the upper bound 2n - 2 is sharp.展开更多
The 3-ary n-cube,denoted as Qn3,is an important interconnection network topology proposed for parallel computers,owing to its many desirable properties such as regular and symmetrical structure,and strong scalability,...The 3-ary n-cube,denoted as Qn3,is an important interconnection network topology proposed for parallel computers,owing to its many desirable properties such as regular and symmetrical structure,and strong scalability,among others.In this paper,we first obtain an exact formula for the minimum wirelength to embed Qn3 into grids.We then propose a load balancing algorithm for embedding Qn3 into a square grid with minimum dilation and congestion.Finally,we derive an O(N2)algorithm for embedding Qn3 into a gird with balanced communication,where N is the number of nodes in Qn3.Simulation experiments are performed to verify the total wirelength and evaluate the network cost of our proposed embedding algorithm.展开更多
基金Acknowledgements The author would like to thank the anonymous referees for their valuable suggestions. This work was supported by the Natural Science Foundation of Fujian Province （No. 2011J01025）.
文摘The k-ary n-cube Qkn （n ≥2 and k ≥3） is one of the most popular interconnection networks. In this paper, we consider the problem of a fault- free Hamiltonian cycle passing through a prescribed linear forest （i.e., pairwise vertex-disjoint paths） in the 3-ary n-cube Qn^3 with faulty edges. The following result is obtained. Let E0 （≠θ） be a linear forest and F （≠θ） be a set of faulty edges in Q3 such that E0∩ F = 0 and ｜E0｜ ＋｜F｜ ≤ 2n - 2. Then all edges of E0 lie on a Hamiltonian cycle in Qn^3- F, and the upper bound 2n - 2 is sharp.
基金the National Key Research and Development Program of China under Grant No.2018YFB1003201the National Natural Science Foundation of China under Grant Nos.61572337,61602261,61672296,and 61872257+4 种基金Jiangsu High Technology Research Key Laboratory for Wireless Sensor Networks Foundation under Grant No.WSNLBKF201701the Scientific & Technological Support Project of Jiangsu Province of China under Grant Nos.BE2016777,BE2016185,and BE2017166China Postdoctoral Science Foundation under Grant No.172985the Natural Science Foundation of the Jiangsu Higher Education Institutions of China under Grant No.17KJB520036Jiangsu Planned Projects for Postdoctoral Research Funds under Grant No.1701172B.
文摘The 3-ary n-cube,denoted as Qn3,is an important interconnection network topology proposed for parallel computers,owing to its many desirable properties such as regular and symmetrical structure,and strong scalability,among others.In this paper,we first obtain an exact formula for the minimum wirelength to embed Qn3 into grids.We then propose a load balancing algorithm for embedding Qn3 into a square grid with minimum dilation and congestion.Finally,we derive an O(N2)algorithm for embedding Qn3 into a gird with balanced communication,where N is the number of nodes in Qn3.Simulation experiments are performed to verify the total wirelength and evaluate the network cost of our proposed embedding algorithm.
