基于超立方体的双Petersen图连接的互联网络研究

基于Petersen图的短直径与超立方体节点的高可连接性,提出了一种新型的互连网络拓扑结构——基于超立方体的双Petersen图连接的互联网络PHP(n);并对其拓扑性质进行了研究.研究表明PHP(n)网络具有正则性和良好的可扩展性与容错性.另外,还设计了PHP(n)网络上的单播、广播路由算法,证明了其通信效率均为n+...     

基于交叉立方体环连接的Petersen图互联网络研究

利用环的简单扩展性以及Petersen图的短直径与交叉立方体节点的高可连接性,提出了一种新型互联网络RCP(n),并对其性质进行了一些研究,证明了RCP(n)网络不但具有正则性以及良好的可扩展性,同时还具有比Qn,HP(n),RHP(n)网络更短的直径和更小的构造开销。     

一种新的并行计算机网络模型及其路由算法

为了提高并行计算机的通信效率，基于Petersen图提出了一种新的网络结构-GP（n，k）网络．该结构继承了Petersen图简单的拓扑结构，同时具有良好的可扩展性．主要研究了其中一类GP（n，k）网络即GP（i^2，i）的拓扑性质，给出了它优于2-Dtorus的直径．最后设计出GP（i^2,i）的单播及多播路由算法．     

广义Petersen图的最小点覆盖集

点覆盖问题是一个著名的NP完全问题.本文对广义Petersen图P(n,2)的精确最小点覆盖数进行研究,讨论并证明了广义Petersen图P(n,2)的最小点覆盖数,给出了最小点覆盖集的构造方法.     

多跳无线Ad hoc网络分区树路由协议ASTRP

为了降低路由的更新代价和提高路由的有效性,提出了一种用于多跳无线Ad hoc网络的路由协议ASTRP(Ad hoc Subarea Tree Routing Protocol).ASTRP属于分级路由协议,通过建立分区树,在逻辑上将网络划分为多个分区,每个分区由一棵树组成.由于分区树具有路由选择功能,所以ASTRP具有先应式路由协议和按需路由协议的功能特点.文中还给出了ASTRP的建立过程,证明了ASTRP的正确性,并对其路由存储代价和路由更新代价进行了分析.结果表明,与其它分级路由协议相比,ASTRP将节点的失效影响限定在分区以内及有限的根节点之间,其路由更新代价明显降低.     

广义Petersen图的可扩性

利用广义 Petersen图的性质 ,给出了几个重要的引理 ,证明了当 k≥ 3,n≠ik( i=2 ,3)时 ,广义 Petersen图 GP( n,k)是 2—可扩的。     

广义Petersen图G(2m+1,m)的交叉数

先利用去边的方式证明了广义Petersen图G(2m+1,m)的交叉数的下界是3,然后证明它的交叉数就是3.     

一种带有纽结分支的内在链图

针对于Petersen图P9进行研究,利用两个Petersen图K3,3,1与中间边组成的图的方法来形成petersen图中的P9,本文得到了一种带有纽结分支的内在链图H(93),并证明了该定理.     

广义Petersen图GP(n,k)的着色

本文研究广义Petersen图GP(n,k)的点着色、边着色和点-边全着色,得到广义Petersen图GP(n,2)的点色数、边色数和全色数,同时还得到当n为偶数,k为奇数时,该广义Petersen图GP(n,k)满足点-边全着色猜想等结论.     

C-Tree:一种多维对象的动态索引方法

在X－Tree的基础上，提出了一种新的动态索引方法C－Tree。该方法继承了X－Tree超节点的观点，针对X－Tree分裂算法的不足，给出了新的分裂算法，并通过理论和实验数据，证明了C－Tree的整体性能优于X－Tree。