[1]杜立智,张晓龙.一个高效的3SAT到Hamilton环转化方法[J].南京理工大学学报(自然科学版),2013,37(04):506.
 Du Lizhi,Zhang Xiaolong.Efficient way to transform 3SAT to Hamilton cycle[J].Journal of Nanjing University of Science and Technology,2013,37(04):506.
点击复制

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

《南京理工大学学报》(自然科学版)[ISSN:1005-9830/CN:32-1397/N]

卷:
37卷
期数:
2013年04期
页码:
506
栏目:
出版日期:
2013-08-31

文章信息/Info

Title:
Efficient way to transform 3SAT to Hamilton cycle
作者:
杜立智张晓龙
武汉科技大学 计算机科学与技术学院,湖北 武汉 430065
Author(s):
Du LizhiZhang Xiaolong
College of Computer Science and Technology,Wuhan University of Science and Technology, Wuhan 430065,China
关键词:
计算机算法 哈密尔顿环 三元可满足性问题 非确定性多项式时间完全
Keywords:
computer algorithm Hamilton cycle 3-satisfiability problem nondeterministic polynomial time complete
分类号:
TP301.5
文献标志码:
A
摘要:
为了得到将三元可满足性问题(3-Satisfiability problem,3SAT)直接转化为哈密尔顿环(Hamilton cycle)的高效转化方法,该文以长年对哈密尔顿环研究计算所探索出的规律为基础进行研究。通过对各种可能实现转化的图形组合进行全面的比较分析,得出用无向图的两个节点模拟3SAT的一个变量,用无向图的13个节点模拟3SAT的一个子式的方法,实现了3SAT到哈密尔顿环的高效转化。研究结果表明:该转化所需要的节点数及其边数是最优的。
Abstract:
In order to get the most efficient transform from 3-Satisfiability Problem(3SAT)to Hamilton cycle,this paper does this research based on the author's long time study and calculation of the Hamilton cycle.With the careful comparison and analysis of all kinds of possible graphs which can do this transform,this paper gets the final method:2 vertices to denote a variable of the 3SAT and 13 vertices to denote a clause of the 3SAT,to realize the high efficient transform from 3SAT to Hamilton cycle.The results show that this method needs the least number of vertices and edges.

参考文献/References:

[1] Aho A V,Hopcroft J E,Ullman J D.The design and analysis of computer algorithms[M].New York:Addison Wesley Publishing Company,1974:384-400.
[2]陈志平,徐宗本.计算机数学[M].北京:科学出版社,2001:97-105.
[3]Cook S.The complexity of theorem proving procedures[A].Proceedings of Third Annual ACM Symposium on Theory of Computing[C].New York,USA:Association for Computing Machinery,1971:151-158.
[4]Gurevich Y,Shelah S.Expected computation time for Hamiltonian path problem[J].SIAM J on Computing,1987,16(3):486-502.
[5]Gurevich Y.Complete and incomplete randomized NP problems[A].28th Annual Symposium on Foundations of Computer Science[C].Washington,DC,USA:IEEE Computer Society,1987:111-117.
[6]Krivelevich M,Lubetzky E,Sudakov B.Hamiltonicity thresholds in achlioptas processes[J].Random Structures and Algorithms,2010,37(1):1-24.
[7]Iwama K,Nakashima T.An improved exact algorithm for cubic graph TSP[A].Proceedings of 13th Annual International Computing and Combinatorics Conference(COCOON)[C].Heidelberg,USA:Springer-Verlag Berlin,2007:108-117.
[8]Christofides D,Kuhn D,Osthus D.Edge-disjoint Hamilton cycles in graphs[J].J Combin Theory B,2012,102(5):1035-1060.
[9]Krivelevich M,Samotij W.Optimal packings of Hamilton cycles in sparse random graphs[J].SIAM J Discrete Mathematics,2012,26(3):964-982.
[10]申晓宁,李涛,张敏.一种基于模糊逻辑引入偏好信息的多目标遗传算法[J].南京理工大学学报,2011,35(2):245-251.
Shen Xiaoning,Li Tao,Zhang Min.Muti-objective optimization genetic algorithm incorporating preference information based on fuzzy logic[J].Journal of Nanjing University of Science and Technology,2011,35(2):245-251.
[11]王海梅,周献中.一种限制搜索区域的最短路径改进算法[J].南京理工大学学报,2009,33(5):638-642.
Wang Haimei,Zhou Xianzhong.Improved shortest path for restricted searching area[J].Journal of Nanjing University of Science and Technology,2009,33(5):638-642.
[12]董刚,范宝春.气相爆轰模拟的动态存储/删除算法[J].南京理工大学学报,2009,33(5):576-580.
Dong Gang,Fan Baochun.Dynamical storage-deletion algorithm for gaseous detonation modelling[J].Journal of Nanjing University of Science and Technology,2009,33(5):576-580.
[13]王辉,赵文会,施佺.复杂网络中节点重要性Damage度量分析[J].南京理工大学学报,2012,36(6):926-931.
Wang Hui,Zhao Wenhui,Shi Quan.Analysis on damage measure of vertex importance in complex networks[J].Journal of Nanjing University of Science and Technology,2012,36(6):926-931.
[14]Karp R.Reducibility among combinatorial problems[J].Complexity of Computer Computations,1972,3:85-103.
[15]Garey M,Johnson D,Tarjan R.The planar Hamiltonian circuit problem is NP-Complete[J].SIAM J COMPUT,1976,5(4):704-714.
[16]朱保平,周良,刘凤玉.基于细胞自动机的公钥密钥体制研究[J].南京理工大学学报,2007,31(5):612-616.
Zhu Baoping,Zhou Liang,Liu Fengyu.Public-key cryptosystem based on cellar automata[J].Journal of Nanjing University of Science and Technology,2007,31(5):612-616.

备注/Memo

备注/Memo:
收稿日期:2012-05-06 修回日期:2013-05-15
作者简介:杜立智(1964-),男,副教授,主要研究方向:计算机算法,计算复杂性,E-mail:dlz95@sohu.com。
更新日期/Last Update: 2013-08-31