Solving the Longest Path Problem Using a Biologically DNA Computational Model

摘要

DNA computing has been applied in wide fields such as graph theory, path search problem and combinatorial problem. DNA computing, with the advantages characteristic of parallelism and high-density storage, is more suitable used to solve many complicated problems. The longest path problem aims to find a head-to-tail path with maximum vertex number in a given undirected graph. Based on biological molecular computation, the paper describes a new DNA procedure to solve longest path problem in O(n) time complexity, which greatly simplifies the complexity of the computation.