粘贴与删除系统求解最短有向路的DNA计算模型

最短有向路问题是在一个有向网络中的两个指定顶点之间找出一条具有最小权的有向路,它在工程实践中具有广泛的应用。粘贴系统与删除系统是DNA计算形式模型中的两种基本模型。论文利用粘贴与删除系统的巨大并行性给出了求解图最短有向路问题的DNA计算模型及其实现算法。

具有禁止诱导特殊短有向路的超欧拉有向图（英文）

D是严格有向图(无环与重弧),如果D有一个生成欧拉子有向图,则称D是超欧拉的.文章主要研究一个强有向图成为超欧拉的禁止诱导子有向图的图条件.如果H■D,V(H)={x_1,x_2,x_3,x_4}而且A(H)={(x_2,x_1),(x_3,x_2),(x_3,x_4)},则称H是有向路P'4;如果H■D,V(H)={x_1,x_2,x_3,x_4}而且A(H)={(x_1,x_2),(x_2,x_3),(x_4,x_3)},则称H是有向路P″4.定义了有向图类F(Γ,h),主要研究了当h'≥h_4(h″≥h_4)且h'_4(h″_4)是最小值时,每个有向图在F(P'_4,h')(F(P″_4,h″))中是超欧拉的.

两个组合优化问题的算法设计

以有向赋权图为工具,通过对满足限制条件的最短有向路径问题的讨论,给出了两个组合优化问题——大学教学计划的编排问题和交通网络中路径规划问题的有效算法,并通过实例进行了算法分析.