基于图着色的极大团求解算法

极大团问题是图论中一个经典的组合优化问题,也是一类NP完全问题,在国际上已有广泛的研究。作者在对其他现有极大团求解算法进行研究之后,设计了一种基于图着色思想的极大团求解算法。基本思想是通过不同的方式对随机图的相应补图进行顶点着色,寻找出所有顶点的极大独立集。而后返回到原图之中找出极大团,并且通过比较删减寻找到随机图的所有极大团。     

基于粘贴模型的最大团问题算法

对粘贴模型的组成、基本实验及其生化实现过程进行了分析,根据解决最大团问题的需要简化了粘贴模型.在粘贴模型中,提出了基于电泳技术和分离实验的DNA序列检测方法,可以检测多种存储链.基于分离实验提出了最大团问题的DNA算法,并给出其生化实现过程:先形成所有非空顶点子集的初始解空间;然后对每条边用分离实验进行检测,保留全部满足不相邻要求的顶点子集,从而得到全部团;再通过电泳实验得到全部最大团.通过检测实验输出实验结果,证明了算法的可行性和有效性.     

一种基于DNA自组装模型求解最大团问题的算法

基于tiles理论模型和已有DNA自组装模型,结合最大团问题给出基于DNA自组装模型的算法设计,得到具体设计初始分子、规则分子和检测分子所需的DAE块种类.在此基础上采用荧光标记和凝胶电泳生物操作提出了一种求解最大团问题算法.该算法设计tiles的种类为Θ(n2+|E|),其生物操作复杂性为Θ(1).此算法降低了实验的复杂度,而且保证了实验的易操作性和结果的准确性。     

哈林图中划分成完美对集问题的线性算法

图G=(V,E),正整数K≤|V|,G的顶点是否能划分成k≤K个不相交的集合V1, V2,…,Vk, 使得对于i∈{1,…,k},由Vi诱导的子图是一个完美对集.这个问题是一个NP完全问题.给出在哈林图上求最小K值的算法.算法的时间复杂度是O(n).     

小边概率条件下较小植入团的算法

针对植入团问题是平均情况复杂性理论的一个中心问题,将带植入团的随机图模型进行推广,提出小边概率条件,使得边概率可以随着顶点数目的增大而变小.使用随机算法分析中的概率工具,改进文献中算法的分析,证明在小边概率条件下,存在以很大概率找到推广模型中较小的植入团的多项式时间随机算法.     

华中科技大学学报(自然科学版) 2017年 第45卷 总目次

将最大团求解算法融入到极大团枚举算法中,提出了两种带极大团下限的极大团枚举算法及多种预处理筛选策略,通过迭代将不可能包含在极大团中的部分点与边删除,使得搜索空间大幅减小.在搜索策略上,将求解最大团问题的贪心染色算法、增量MaxSAT推理算法与极大团枚举算法相融合,并结合最佳筛选策略,提出了染色-关键点融合算法BKFC(Bron-Kerbosch with filtering and coloring)和基于增量MaxSAT推理的枚举算法BKFS(Bron-Kerbosch with filtering and MaxSAT).结果表明:在多个大型算例上,BKFC算法平均时间仅为加入预处理的改进经典算法的68.8%;由于经典算法无法在大型算例上运行,在小数据测试中,BKFC算法平均时间仅为没有预处理策略的经典算法的2.2%.     

大规模稀疏图的极大团枚举算法

将最大团求解算法融入到极大团枚举算法中,提出了两种带极大团下限的极大团枚举算法及多种预处理筛选策略,通过迭代将不可能包含在极大团中的部分点与边删除,使得搜索空间大幅减小.在搜索策略上,将求解最大团问题的贪心染色算法、增量MaxSAT推理算法与极大团枚举算法相融合,并结合最佳筛选策略,提出了染色-关键点融合算法BKFC(Bron-Kerbosch with filtering and coloring)和基于增量MaxSAT推理的枚举算法BKFS(Bron-Kerbosch with filtering and MaxSAT).结果表明:在多个大型算例上,BKFC算法平均时间仅为加入预处理的改进经典算法的68.8%;由于经典算法无法在大型算例上运行,在小数据测试中,BKFC算法平均时间仅为没有预处理策略的经典算法的2.2%.     

基于测定PDM问题的一类积分方程的求解

给出在光纤通信中测定PMD问题中得到的一个积分方程的数值解法,并证明解的唯一性.该解法还可以进一步推广,是线性算子的定义域与值域不相交的情况下,求解线性非齐次方程的一种较简单实用的算法.     

最大团问题的三链DNA计算模型

本文研究利用三链DNA求解最大团问题。首先将最大团问题中的顶点编码为DNA片段,进行生化反应,组合成所有可能的情况,然后利用三链模型对解进行筛选,最终得到图的最大团。该模型降低了编码的复杂度,提高了检测效率,其他的NP(Non-deterministic Polynomial)问题也可用此方法来求解。     

一类变换图的团

1980年,著名的图论专家Richard A.Brualdi提出了关于变换图G (R,S)直径的Brualdi猜想,但至今仍悬而未决.为了研究变换图G (R,S)的结构,定义一类变换图G (R*, S*),其中,R*=(r1,r2)且S*=(1,?,1),得到G (R*,S*)中的顶点是一个团的充分必要条件.变换图G (R*, S*)中的团局部刻画了其内部结构特征.当r≤■时,G (R*, S*)的最大团含有的点数为n-r+1. G (R*, S*)中k-团的个数■.相同类型的不同最大团没有公共边. G (R*, S*)中所有的1-型最大团和所有的0-型最大团恰是G (R*, S*)的两种最大团划分,且任意两个同类型的最大团无重复边.根据G (R*, S*)的团的性质,对变换图G (2,4)、G (2,5)和G (2,6)进行作图.