超立方体网络的容错哈密顿Laceability

超立方体网络Qn是著名的互连网络之一.证明了在具有fav对不相交的相邻点对集Fav和fe条边集Fe发生故障的n维超立方体网络Qn(n≥3)中,如果0≤fav≤n-3,2fav+fe≤2n-5,且每个非故障点至少与2条非故障边相关联,则Qn-{Fav∪Fe}是哈密顿Laceable.该结果推广了现有文献的相关结果.     

关于局部扭立方体的反馈数

确定一般网络(或图)的最小反馈点集问题属NP难问题.n维局部扭立方体网络Qltn是n维超立方体网络Qn的变形且是一类重要的互连网络拓扑结构,其拥有的某些性质优于Qn.根据Qltn顶点集合中最后一位字节不同的特点,将其顶点集合划分为两个不相交的子集,通过构造极大无圈子图得到反馈数的上界,并证明了对任意正整数n≥2,存在常数c∈(0,1)使得反馈数为f(n)=2n-1(1-c/(n-1)).     

容错超立方体网络的圈嵌入

证明了对于有fv个故障点和fe条故障边的容错超立方体网络Qn, 如果fv fe≤2n-4, fe≤2n-5,n≥3且每个节点至少保留两条非故障边,那么Qn中存在长至少为2n-2fv的非故障圈. 这个结果改进了许多已知结果.     

超立方体网络的边容错二部泛连通度

证明了对于至多有n-1条故障边的容错超立方体网络Qn,如果它正好有n-1条故障边但不关联于同一个顶点, 那么对于Qn中任意两点u和v,存在一条长为l的uv非故障路, 路长l满足dQn(u,v) 2≤l≤2n-1且2|(l-dQn(u,v)).这改进了许多已知结果.     

变形超立方体的圈和路嵌入(英文)

作为超立方体网络Qn的变形,n维变形超立方体VQn具有许多优于超立方体所具有的性质.这里证明了对任何整数l∈[4,2n],VQn中每条边被包含在长度为l的圈中除非l=5;对任何顶点对(x,y)和整数l∈[d,2n-1],其中,d为这两点之间的距离,VQn中存在长度为l的xy路除非当d=1时l=2,4.     

折叠超立方体网络的t/k诊断问题

为提高系统故障诊断的诊断度,Somani 和Peleg提出了t/k诊断故障策略. n维折叠超立方体网络是具有2n个顶点,(n+1)2n-1条边的(n+1)-维正则图,它是n维超立方体网络增加2n-1补边得到的.中证明了当n≥6和1≤k≤n+1时n维超立方体网络是t/k可诊断的,其中t=(k+1)(n+1)-1/2(k+1)(k+2)+1.     

超立方体网络广播容错路由算法

研究了具有大量错误结点的超立方体网络中的广播容错路由算法.假定Hn是一个局部3维子立方体连通的n维超立方体网络,并且每一个基本的3维子立方体中分别最多有1个和2个错误结点,从理论上证明了在最坏情况下基于shouting广播通信模式的广播容错路由算法分别经过最多1.5(n-1)和2(n-1)时间步,就可以将源结点的信息广播到Hn中的所有正确结点中;通过实验验证了在均匀和独立的错误结点分布情况下广播时间步的上界实际上只有n+1,支持了理论分析结果.     

广义超立方体的广义连通度

k元n方体是著名的超立方体网络的推广。针对k元n方体的广义3-连通度问题,证明了对任意的整数k≥3和n≥1,k元n方体中存在2n-1棵内部不交的连接任意3个顶点的树。     

广度优先搜索算法在交叉立方体中的应用

给出了互连网络上的广度优先搜索算法，将其应用到交叉立方体上可以得到交叉立方体的广度优先生成树。连通图的广度优先生成树的树高不会超过该图其他同根生成树的高度。利用这一性质，通过分析交叉立方体的广度优先生成树的特征，给出了n维交叉立方体CQ的直径为[(n 1)／2]的另外一种证明方法；该算法可以用来求解单源节点最短路径问题。并为讨论新的互连网络拓扑结构的直径和故障直径问题以及单源广播算法提供了一条新的思路。     

折叠立方体网络Qfn Laplace矩阵的谱

图G的Laplace矩阵的谱是由L(G)的所有特征值构成的.研究了一类重要的互连网络拓扑结构折叠立方体网络Qfn的Laplace矩阵的谱.由于折叠立方体Qfn是在超立方体Qn的基础上增加了互补边形成的,利用从Qn的Laplace矩阵An构造Qfn的Laplace矩阵Bn的对偶矩阵Cn=An-I*n+In的方法,确定了Bn和Cn的关系为︱Bn+1︱=︱Bn ︱︱Cn-4In︱,从而确定了折叠立方体的Laplace矩阵Bn的谱.     

条件容错的增强立方体边不交路（英文）

研究增强立方体,它是超立方体显著的变形,并且是从立方体上添加一些补边得到,着重讨论边容错的增强立方体边不交路.主要结果:n维增强立方体Q_(n,k)(n≥3,2≤k≤n-1)是S-强Menger边连通的(|S|≤2n-3).     

故障3-元n-立方体的哈密顿圈嵌入

哈密顿圈嵌入问题是研究互连网络并行计算中最重要问题之一.在文章中,我们考虑带故障点的3-元n-立方网络Qn3的哈密顿圈嵌入问题并得到如下结果.给定一个具有至多2n-2个故障点的集合F,对Qn3-F中任意边,除一种特殊情况外,Qn3-F中都有一个哈密顿圈包含这条边,即Qn3-F是几乎-边哈密顿的.     

超立方体网络的限制边连通性

m-限制边割将连通图分离成阶不小于m的连通分支,图G的最小m-限制边割所含的边数称为图的m-限制边连通度.本文给出了n立方体的m-限制边连通度的表达式,由此推出：当m≤2（n/2）-1或m=2 k≤2n-1（k为任意正整数）时,超立方体Qn是极大m-限制边连通的.     

n维超立方体中点不交的最短路径

最短路径问题一直是并行计算系统的研究热点之一。主要研究了n维超立方体Qn上的点不交的最短路径问题,采用数学归纳法证明了如下结果:Qn中任意两节点s、t之间一定存在k条长度为k的点不交最短路径,其中k=H(s,t)(k≤n)为s、t之间的Hamming距离。     

BC网络的限制边连通度

互连网络的可靠性评估对于多处理系统的设计和维护是非常重要的。限制边连通度是互连网络可靠性评估的一个重要参数,因此,研究限制边连通度对互联网络的可靠性评估具有重要意义。通过研究n-维双射连通互连网络(简称BC网络)的h-限制边连通度的性质,可推导得到n-维BC网络的h-限制边连通度的值。另外,因为BC网络包含若干著名的网络模型,比如,超立方体、莫比乌斯立方体、交叉立方体、扭立方体、生成扭立方体、广义扭立方体和M立方体,所以,应用推导得到的结果可以得出这些网络的h-限制边连通度。     

边故障超立方体中两条无故障点不交路

文中用归纳假设法证明了结论:当n≥时,令超立方体中的边故障集|F|≤n-3, 设x1,x2,y1,y2是Qn中4个顶点,使得距离d(x1,y1)和距离d(x2,y2)都是奇数,则在Qn-F中存在两条路P1和P2,使得V(P1)nv(P2)=ф , 这里P1连接x1和y2, P2连接x2和y2, 而且边故障集|F|=n-3(n≥3)是最佳上界.     

基于超立方体Q_n节点编码的边不交最优路径

基于超立方体节点编码的特点,得到了n维超立方体Qn中任意两节点s、t之间的两条并行最优路径算法.该算法共包括了11步骤,在最坏的情况下需要执行2n2+4n2次运算,它的时间计算复杂度为O(n2),属于多项式算法.     

完全对换图的广义3-连通度（英文）

令S■V(G)κ.G(S)表示图G中内部不交的S-树T1,T2,…,Tr的最大数目r,使得对任意i,j∈{1,2,…,r}且i≠j,有V(Ti)∩V(Tj)=S,E(Ti)∩E(Tj)=.定义κk(G)=min{κG(S)|S■V(G),且|S|=k}为图G的广义k-连通度,其中k是整数,且2≤k≤n.完全对换图在网络中是重要的一类Cayley图.该文证明了n-维完全对换图CTn的广义3-连通度是n(n-1)/2-1,也就是说,对于CTn的任意三个点,存在n(n-1)/2-1个连接它们的内部不交的树.     

扭n立方体中的边不交Hamilton圈

网络图的Hamilton性是图论、计算机网络理论中的重要研究议题，超立方体及其变体由于其良好的网络参数、拓扑结构吸引了众多学者的关注和研究，并将之广泛地应用于许多实际领域中．结合Lee距离Gray码理论证明了扭n方体中存在[n／2]个边不交Hamilton圈，并且给出这些边不交Hamilton圈的生成方法．     

变形超立方体网络的可靠性分析

作为超立方体网络的变形, n维变形超立方体VQ_n是Cheng和Chuang于1994年提出来的,它具有许多超立方体所具有的优良性质, 比如正则性和递归结构.证明了:VQ_n 的连通度和边连通度都等于n,限制连通度和限制边连通度都等于2n-2. 这个结果意味着,为了使VQ_n不连通且不含孤立点, 至少有2n-2个点或者边要同时发生故障.