一个高效的3SAT到Hamilton环转化方法

• 作者: 张晓龙 杜立智
• 来源期刊: 南京理工大学学报（自然科学版）
• 学科: 工学
• 关键词: 计算机算法 哈密尔顿环 三元可满足性问题 非确定性多项式时间完全
• 年，卷（期）: 2013,（4）
• 页码范围: 506-510
• 页数: 5页
• 分类号: TP301.5
• 字数: 3577字
• 语种: 中文

摘要

为了得到将三元可满足性问题(3-Satisfiability problem,3SAT)直接转化为哈密尔顿环(Hamilton cycle)的高效转化方法,该文以长年对哈密尔顿环研究计算所探索出的规律为基础进行研究.通过对各种可能实现转化的图形组合进行全面的比较分析,得出用无向图的两个节点模拟3SAT的一个变量,用无向图的13个节点模拟3SAT的一个子式的方法,实现了3SAT到哈密尔顿环的高效转化.研究结果表明:该转化所需要的节点数及其边数是最优的.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	张晓龙	武汉科技大学计算机科学与技术学院	49	652	13.0	24.0
2	杜立智	武汉科技大学计算机科学与技术学院	21	73	4.0	7.0