|Table of Contents|

Efficient way to transform 3SAT to Hamilton cycle

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

Issue:
2013年04期
Page:
506-
Research Field:
Publishing date:

Info

Title:
Efficient way to transform 3SAT to Hamilton cycle
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
PACS:
TP301.5
DOI:
-
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:
-
Last Update: 2013-08-31