The Hamiltonian Cycle Problem Based on DNA Computing
Wenbin Liu, Xiangou Zhu, and Lin Gao
The Hamiltonian cycle problem is one of the famous problems in the field of DNA computing. Previous works have been mainly focused on solving instances in digraph. While the main drawback of these works is that they are hardly introduced to handle problems in undirected graph. In this paper we present a DNA algorithm to solve the Hamiltonian Cycle Problem in undirected graph based on a solid phase chemistry. Binary strands are used to represent the edge sequences of a graph. As single-stranded DNA molecules, which represent the edge sequences of the graph, are synthesized on a surface step by step, a destroy technique is employed to remove all the illegal paths generated in each cycle. This greatly reduces the number of DNA molecules necessary for the computation. Hence our algorithm can be applied to a larger scale instance compared with other DNA algorithms.