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

来源 :Science in China(Series F:Information Sciences) | 被引量 : 0次 | 上传用户:lgfgdf
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
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. 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 It is also proved that there exists a Hamiltonian cycle in the RP-1 (k) network. So the ring with 9 * k nodes can be embedded into the RP-1 (k) network After defining the sequence of the 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.
其他文献
随着社会经济的快速发展,对轨道交通行业提出了更高的要求.为了适应新形势下轨道发展趋势,必须跟紧步伐,提高工作效率,同时还需对我们的产品不断优化.本文主要介绍了变流器设
茶树原产于亚热带,属多年生常绿作物,具有喜温湿耐阴怕旱的习性;气温过高,雨量过少,茶树生长就会受到抑制。我所地处赣中丘陵,气候特点,往往每年七、八月间,晴多雨少,温度高
目的:通过建立新西兰大白兔阻塞性睡眠呼吸暂停低通气综合征(Obstructive Sleep apnea-hypopnea Syndrome,OSAHS)的动物模型,观察下颌前移矫治器(mandible advanced device,
苧麻雄性不育性状有的在无性繁殖世代中天然存在,有的在有性繁殖后代中也会产生。这些雄性不育系在自然传粉的情况下,都能恢复结籽,其子代具有不同程度的超亲优势。 一、园
模型是否能够构成著作权法上的模型作品从而获得著作权的保护在学理上仍具有争议.模型的可版权性的基础是模型及其来源的关系,实践中,模型的类型可具象为三类,包括实物、作品
为促进城市高压输电线路的运行更加稳定,全面满足人们在电能使用方面的需求,本人对高压输电线路在线监测技术的应用进行分析.首先,概述了在线监测技术的基本功能.而后,列举了
随着科技水平不断提升,我国城市轨道交通迎来了新的发展契机.架空刚性接触网作为城市轨道交通的全新接触悬挂方式,与柔性接触网之间有着较大差异性,不仅体现在设计、安装上,
5月21日,全国政协十三届三次会议开幕,这次全国两会是在疫情防控常态化条件下召开的.在全国两会来临之际,如何利用党报新媒体的特有优势,凝聚夺取疫情防控和经济社会发展双胜
期刊
我县是福建省的主要花生产区之一。一九七四年我们就开展了对花生根瘤菌剂和钼酸铵单独施用与混合施用的试验研究工作。小区试验和大田示范表明,钼酸铵和根瘤菌剂混合施用与
一九七八年九月中旬在四川省召开的全国棉花杂种优势利用现场观摩学术讨论会上,重点参观讨论了棉花洞A雄性不育系。现将洞A不育系简介如下。棉花洞A雄性不育系研究与利用的