最大流问题的DNA计算两阶段法

• 作者: 周康 王子成 许进
• 来源期刊: 华中科技大学学报（自然科学版）
• 学科: 工学
• 关键词: 最大流 DNA计算 Δ-松弛网络 增广路
• 年，卷（期）: 2005,（8）
• 页码范围: 104-107
• 页数: 4页
• 分类号: O157.6|TP301.5
• 字数: 3951字
• 语种: 中文
• DOI: 10.3321/j.issn:1671-4512.2005.08.033

摘要

给出了最大流问题的DNA计算两阶段法:第一阶段采用路序问题DNA算法得到包括所有增广路的路集,算法有两点改进,即采用等码长编码和不进行排序,这减少了生化实验时间.第二阶段算法思路是:设置一个逐步减小的增量Δ,对每个确定的Δ值从第一阶段得到的路集中寻找并增广容量不小于Δ值的增广路,对整数容量网络,当Δ<1时获得最大流.证明了算法的正确性和复杂性,并指出在以增广路为基础的最大流算法中,本算法复杂度最低,这说明DNA计算和电子计算相结合的巨大优势.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	周康	武汉工业学院数理科学系	69	557	14.0	20.0
2	许进	华中科技大学控制科学与工程系	117	2149	25.0	39.0
3	王子成	华中科技大学控制科学与工程系	4	27	2.0	4.0