基于容量约束的深空接触图路由算法

为有效利用节点间通信机会保证数据的可靠传输,提出一种基于容量约束的接触图路由算法。一方面,该算法通过比较节点接触的剩余容量和预计容量损耗计算最早到达路径,避免所选路径后续节点没有足够的容量。另一方面,数据包的转发节点数由反馈的链路状态和网络拓扑关系自适应决定,在网络性能和资源消耗中得到平衡。仿真表明,该算法能提高数据包投递率最高27.7%,端到端传输时延最高降低24.5%,有效应对深空恶劣环境的影响。     

n-星形图的广播距离

广播是信息在网络上的传播过程。本文研究信息在n-星形图上的广播距离，得到其上界是2n[logn]－2[logn] 1＋1，下界是[logn!]。     

一类置换群图的路由算法研究

群Cayley图是并行处理系统中研究可靠通信网络拓扑结构及路由算法的有力工具.置换群Cayley图具有结构复杂、灵活多变的特点, 而且具有良好网络所要求的性能指标.研究置换群Cayley图的路由算法是设计该类互连网络模型的重要内容之一.借助基于极小对换生成集的群Cayley图的对换树,设计了该类群Clayey图的路由算法,其时间复杂度为O(n2).同时运用置换群元素的对换分解方法,给出了两个特殊群Clayey图的最优路由算法.     

基于图搜索的网络路由算法的复杂度分析

本文以图搜索问题作为计算机网络呼由选择问题的数学模型，探讨了路由算法的几个基本性质。对于网络路由算法的空间耗费，本文的主要结论是，（１）．不可能有最大空间耗费小于０（Ｍ）的路由算法，（Ｍ是网络中所含的ＩＭＰ个数）；（２）．不存在普遍最优的可采纳路由算法。     

多协议标记交换网络实现流量工程的路由算法

对多协议标记交换网络中实现流量工程的路由算法进行了研究，提出两种TE(流量工程)路由算法．一种是对Dijkstra算法进行改进的、最小化最大带宽利用率的TE路由算法；另一种是根据链路的使用情况赋权值、并综合考虑带宽和跳数限制的最小权值TE路由算法．最后，对两种算法进行了仿真．结果表明，两种算法能在一定程度上避免对部分链路的过度使用，起到均衡负载分布的作用．     

基于Internet AS图的紧凑路由算法研究

紧凑路由算法一直被认为是未来Internet上可扩展路由算法的有力候选者,因为它实现了近似最短路径路由机制的同时,路由表也比BGP(border gateway protocol)路由协议更加紧凑.TZ紧凑路由算法初始地标点的选取是随机生成的,没有充分利用网络拓扑信息,不是很适合真实网络.故分别提出了基于节点度和基于PageRank算法的地标节点选取机制,用于改进TZ紧凑路由算法.在2000年和2006年的Internet AS图上对两种改进算法和TZ算法进行仿真,实验结果表明,两种改进算法的平均路由表大小和平均伸长系数相比于TZ算法均有明显的改进.     

区间图和强弦图的全着色及最优算法

证明对于任意区间图和强弦图－全着色猜想成立，并且给出了区间图和强弦图的最优线性地，其算法复杂度仅为Ｏ（Ｖ＋Ｅ）。     

一个有效的容错路由算法

互连网络中路由容错是网络设计的重要问题之一。作者利用ｎ维超方体模型,研究了互连网络中容错路由问题,包括容许的故障点和故障块的数目和结构,给出了一个有效的点到点路由算法,并分析了该算法的正确性和有效性。     

基于邻居信息交换的机会网络低时延路由算法

提出一种以Epidemic Routing为基础、采用两跳邻居信息交换方式的机会网络低时延路由算法———LDREN,在分组索引的交换过程中交换两跳邻居信息从而增强对本地拓扑的掌握,并优先发送位于最后两跳的数据分组;同时在节点相遇感知过程中借助ECHO消息从节点缓存中删除已到达目的节点的分组.性能分析结果表明,与经典的Epidemic路由算法及其改进算法ARER相比,LDREN在分组端到端时延、分组传送成功率、存储空间占用等方面的性能得到整体提升.     

基于输入交换队列的双向图匹配调度算法的协议模型表示

针对基于定长分组（信元）双向图匹配的输入队列交换机调度算法,提出了算法的统一符号表示与描述方法及其实例．     

完全三部图的线图所生成的二元码

给出了三部图Kn1,n2,n3(n1n2n3)线图生成的二元码,当n1+n2+n3为奇数时,C为[n1n2+n2n3+n1n3,n1+n2+n3-1,n1+n2]2;当n1+n2+n3为偶数时,C为[n1n2+n2n3+n1n3,n1+n2+n3-2,2(n1+n2)]2,其中n3≥n2+2,或者C为[n1n2+n2n3+n1n3,n1+n2+n3-1,2n1+n2+n3-2]2,其中n3n2+2.     

关于图的减边全控制

引入了图的减边全控制的概念,通过对图的边集分裂的方法,得到了一般图的减边全控制数的若干下界,并研究了几类特殊图的减边全控制问题,确定了路P n、圈C n和轮图W n+1的减边全控制数。     

图的反全符号控制数

设G=（V,E）是一个非空图,对于一个函数f∶V（G）∪E（G）→{-1,1},则称f的权重为w（f）=∑x∈V（G）∪E（G）f（x）。若x∈V（G）∪E（G）,定义f[x]=∑y∈NT[x]f（y）。如果对所有的x∈V（G）∪E（G）都有f[x]≤1,则称f是图G的一个反全符号控制函数。G的反全符号控制数定义为γ＊...     

Series-Parallel图的全选择数与全色数

对2-连通Series-Parallel图G，证明了当△（G）≥4时，其全选择数等于△（G） 1；在△（G）≥3时，其全色数等于△（G） 1；对△（G）≠时，其边选择数等于其边色数（即列表染色猜想）。由于外平面图是特殊的Series-Parallel图，本文包含了外平面图的相应染色结论。     

图的反符号边全K-控制数

设G=(V,E)是一个图,一个函数f:E→{-1,+1}如果∑e′∈N(e)f(e′)≤0对于至少k条边e∈E成立,则称f为图G的一个反符号边全k控制函数。一个图G的反符号边全k控制数定义为γkst(G)=max{∑e∈Ef(e)|f为图G的反符边全k控制函数}。本文主要给出了连通图G的反符号边全k控制数γkst(G)的若干上限。     

随机图的邻点可区别 I-全染色算法

针对随机图设计了一种启发式的邻点可区别I 全染色算法,能够求解随机图的邻点可区别I 全色数。该算法根据邻点可区别I 全染色条件,确立了3个子目标函数和1个总目标函数,利用交换规则逐步寻优,直到目标函数值满足要求时结束。给出了详细的算法设计步骤及流程,同时进行了测试和分析,测试结果表明,该算法可以得到随机图的邻点可区别I 全色数,并且算法的时间复杂度不超过O（n3）。     

若干倍图的邻点可区别均匀全染色

研究一些倍图的邻点可区别均匀全染色(AVDETC), 利用构造法和匹配法给出了偶阶完全图、 偶阶圈、 路、 星和轮的倍图的邻点可区别均匀全色数, 并验证了它们满足邻点可区别均匀全染色猜想(AVDETCC).     

若干联图的邻点可区别全染色

研究若干联图的邻点可区别全染色,证明了:当n≥3时,χat(Kn∨Cn)=χat(Kn∨Pn)=2n+1;当n≥4时,χat(Kn∨Wn?1)=χat(Kn∨Fn?1)=χat(Kn∨Sn?1)=2n+1.     

图上的Nash均衡问题算法研究

图对策是一类研究多人参与某种对局而产生的图模型问题,研究的核心在于如何寻找求解Nash均衡点的算法。一般图上求解Nash均衡解是NP-C的,这里从一类特殊的图出发,研究以这类特殊图为底图的对策的Nash均衡问题,并给出了其有效算法。     

开外平面图的边面全色数

一个无割点的外平面图称为开外平面图，如果它的每一个内面的边界至少含有一条外边。本文证明了：若Ｇ为开外平面图，则（ｉ）当△（Ｇ）＝３时，ｘ２３（Ｇ）＝４，当△（Ｇ）≥５时，ｘ２３（Ｇ）＝△（Ｇ）；（ｉｉ）当△（Ｇ）＝２，４时，４≤ｘ２３（Ｇ）≤５，其中ｘ２３（Ｇ）为平面图Ｇ的边面全色数，△（Ｇ）是Ｇ的点最大度。