图顶点m着色的改进算法

对于解决图顶点着色问题，目前较常使用ＤＦＳ算法，而由于该算法存在效率不高问题，故提出ＤＦＳ改进算法，极大提高了该算法的效率，对于较难的图顶点着色问题，利用该改进算法更为有利。     

地图着色问题的粘贴DNA算法

提出多级分离的概念,给出一个多级分离装置的模型,并介绍粘贴模型中的多级分离操作、将地图着色问题转化为可满足性问题、基于粘贴模型的巨大并行性及多级分离的优势,提出解决该问题的粘贴DNA算法。通过一个实例给出实验操作步骤,并对生化反应过程进行模拟,得出具体的着色方案,从而证明了该多级分离装置的有效性以及该算法的可行性。     

图的最小顶点覆盖的粘贴DNA计算模型

本文在对经典粘贴模型以及全信息化的粘贴DNA计算模型的基本方法进行充分讨论的基础上,提出一种用粘贴DNA计算模型解决图的最小顶点覆盖问题的新方案,将数学问题的求解同并行生物操作有效结合.     

图顶点着色问题的质粒DNA计算

图的着色问题是著名的NP问题,有着重要的实际意义。比如通讯系统的频道分配、考试排考场问题等方面有直接应用。图的着色问题采用DNA计算方法很多,有表面DNA计算,粘贴DNA计算。本文提出质粒DNA计算,首先把顶点着色问题转化为求最大独立集问题,然后给出了图顶点着色问题的质粒DNA分子生物实验,利用限制性内切酶的特性切割有边相连的顶点,得到最大独立集,在试验中特别引入了一个备用试管,最后给出一个具体的实例。实例给出具体的着色方案,证明了该质粒DNA算法有效并且是可行的。     

一种求解图着色的单亲遗传算法

给出了一种求解图着色问题的新算法,即单个个体的单亲遗传算法.算法采用顶点序号的聚类编码将个体的某个子串随机分配到其他子串中的变异方法.并对该算法的时间复杂度进行了分析比较,结果表明该算法具有较好的运行效率与收敛速度.     

基于改进的粘贴模型求解图最大独立集的DNA算法

改进的DNA粘贴模型在解决SAT问题时所需的寡核苷酸片段数量有显著降低,对改进的粘贴模型做了进一步的改进,建立了图最大独立集的一种改进的DNA粘贴模型.首先将图的独立集问题转化为可满足性问题,然后利用本文改进的粘贴模型给出了图的最大独立集的DNA算法.最后通过一个实例给出算法实现并求出了最大独立集.     

图的k着色问题的DNA计算模型

DNA计算是一种新的并行计算模式,在解决NP完全问题等方面具有很大的优越性．利用DNA计算的计算特性给出了一个图的k着色问题的DNA计算模型,该算法最多需要3kn（n-1）/2＋6个生物操作即可求出图的色数及相应的着色模式．     

图的最小顶点覆盖问题的质粒DNA计算模型

给出了图的最小顶点覆盖问题的质粒DNA算模型及其实现算法．算法的时间复杂性是O(q),编码最小覆盖问题所需的核苷酸片段种类为n,其中n,q分别是图的规模和边数．在算法中,所用酶的种类也等于图的规模．而且,算法不需要复杂的单链DNA自身退火反应和PCR扩增．     

基于粘贴系统求解无向图最短路径问题的DNA计算模型

提出了用粘贴系统求解赋权无向图中固定端点最短路径的DNA算法。该算法首先将无向图中每条边用两条方向相反的有向边代替,将无向图转化为有向图,同时利用粘贴系统的巨大并行性得到两端点间的所有路径,最后通过探针、电泳等分子生物技术手段获得最短路径,并通过实例说明算法的可行性。     

基于遗传和启发式算法的混合顶点着色算法

图的着色问题是一种典型的NP-完全问题.提出了基于遗传算法和启发式算法的新型混合顶点着色算法,该算法在实现过程中涉及到染色体的编码方法、适应度函数的设计以及遗传算子的选择等.实验仿真结果表明此算法改善了求解的时间复杂度,可以获得问题高质量的解.     

De Bruijn图的均匀顶点染色和有向图线图的一个顶点染色定理

给出了ｎ维ｄ进位Ｄｅ Ｂｒｕｉｊｎ图Ｂ（ｄ，ｎ）的一种均匀顶点ｄ＋１染色，即将其顶点集分拆成顶点个数至多相差１的ｄ＋１个无关集，并证明了关于一般有向图的线图的一个顶点染以定理。     

基于粘贴和删除系统求解旅行商问题的DNA算法

旅行商问题（Traveling Salesman Problem,TSP）是一个典型的NP完全问题.粘贴和删除模型是DNA计算的两个基本计算模型.结合上述两个模型的优点,构造粘贴-删除模型,并利用该模型给出求解旅行商问题一种新的DNA算法.     

关于图染色的算法

本文给出了图上顶点染色,边染色的算法.其中边染色算法是一个非多项式时间的精确算法,该算法是先求出所有极大匹配,然后再求极小匹配覆盖,最后得出最优边染色.顶点染色算法是一个多项式时间的近似算法,该算法的时间复杂性为O(n~3logn),空间复杂性为O(n~3)的近似算法,它是由贪吃策略得到的.对于任意的图,该算法所用的期望颜色数为「log(n 1)」.