|Table of Contents|

Efficient way to transform 3SAT to Hamilton cycle


Research Field:
Publishing date:


Efficient way to transform 3SAT to Hamilton cycle
Du LizhiZhang Xiaolong
College of Computer Science and Technology,Wuhan University of Science and Technology, Wuhan 430065,China
computer algorithm Hamilton cycle 3-satisfiability problem nondeterministic polynomial time complete
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.


[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.
[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.
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.
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.
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.
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.
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.


Last Update: 2013-08-31