检索结果-南通市图书馆

Wide Diameter of Generalized petersen graphs

在线全文

学校读者我要写书评

暂无评论

Journal of Mathematical Research and Exposition 2010年第3期30卷 562-566页

作者： Jun ZHANG Xi Rong XU Jun WANG School of Mathematical Sciences Dalian University of Technology Liaonin9 116024 P. R. China Department of Computer Science Dalian University of Technology Liaoning 116024 P. R. China College of Information Technology Shanghai Ocean University Shanghai 201306 P. R. China

Generalized petersen graphs are commonly used interconnection networks, and wide diameter is an important parameter to measure fault-tolerance and efficiency of parallel processing computer networks. In this paper, we show that the diameter and 3-wide diameter of generalized petersen graph P（rn, a） are both O（m/2a）, where a ≥ 3.

关键词： petersen graph diameter wide diameter.

Wide Diameters of Generalized petersen graphs

在线全文

学校读者我要写书评

暂无评论

Journal of Mathematical Research and Exposition 2004年第2期24卷 249-253页

作者：侯新民王天明中国科学技术大学数学系安徽合肥230026 大连理工大学应用数学系辽宁大连116024

Generalized petersen graphs iare an important class of commonly used in-terconnection networks and have been studied by various researchers. In this paper, weshow that the diameter of generalized petersen graph P(m, 2... 详细信息

关键词： petersen graph generalized Petersell graph diameter wide diameter

The embedding of rings and meshes into RP(k) networks

在线全文

学校读者我要写书评

暂无评论

Science in China(Series F) 2004年第5期47卷 669-680页

作者： LIUFang'ai LIUZhiyong ZHANGYongsheng TheSchoolofInformationManagement ShandongNormalUniversityJinan250014China TheNationalNaturalScienceFoundationofChina Beijing100085China

This paper first investigates the topological properties of RP(k) networks. Then focusing on the embedding of rings and 2-D meshes into the RP(k) network, it is proved that the RP(k) network is a Hamiltonian graph and the ring with 10*k nodes can be embedded into the RP(k) network with load, expansion, dilation and congestion all equal to 1. If there exists a faulty node on each slice in the RP(k) network, throwing off the faulty nodes, the RP-1(k) network is obtained. It is also proved that there exists a Hamiltonain cycle in the RP-1(k) network. So the ring with 9*k nodes can be embedded into the RP- 1(k) network. After that, we discuss the embedding of a 2-D mesh, M1(a, b), into the RP(k) network. By defining the sequence-column-order mapping, the snake-like-column-order mapping and the shortest path mapping, we obtain two ways of embedding a 2-D mesh into the RP(k) network. The performances of the embedding are as follows. In the snake-like-column-order mapping, the dilations are 1, 2, 3, 3 and 2 and the congestion are 1, 3, 4, 5 and 3 respectively when a is equal to 1, 2, 3, 4 and 5. In the sequence- column-order mapping, the dilation is equal to 3 and the congestion is equal to 6 when a is between 6 and 9. The dilation is equal to a/10+2 and the congestion is equal to max{ a/10+1, 6} when a >10. As a special case, the four parameters are also equal to 1 when a is equal to 10.

关键词： interconnection network RP(k) petersen graph network embedding Hamiltonian cycle dilation congestion.

A practical interconnection network RP(k) and its routing algorithms

在线全文

学校读者我要写书评

暂无评论

Science in China(Series F) 2001年第6期44卷 461-473页

作者：刘方爱刘志勇乔香珍 Institute of Computing Technology Chinese Academy of Sciences Beijing 100080 China Department of Computer Science Shandong Normal University Jinan China

Based on petersen graph, a new interconnection network, the RP(k) network, is devel-oped and the properties of the RP(k) network are investigated. The diameter of the RP(k) network is [ k/2] + 2 and its degree is 5. We prove that the diameter of the RP(k) network is much smaller than that of the 2-D Torus network when the number of nodes in interconnection networks is less than or equal to 300. In order to analyze the communication performance in a group of nodes, we propose the concepts of the optimal node groups and the diameter of the optimal node groups. We also show that the diameter of the optimal node groups in the RP(k) network is less than that in the 2-D Torus net-work. Especially when the number of nodes in an optimal node group is between 6 and 100, the diam-eter of the optimal node groups in the RP(k) network is half of that in the 2-D Torus network. Further-more based on the RP(k) network we design a set of routing algorithms which are point-to-point rout-ing, permutation routing, one-to-all routing and all-to-all routing. Their communication efficiencies are [ k/2] +2, k + 5, [k/2] + 2, and k + 5 respectively. The RP(k) network and the routing algorithms can provide efficient communication means for parallel and distributed computer system.

关键词： RP(k) interconnection network the optimal node group routing algorithm petersen graph the network diameter.