DNA Algorithms For The Generalized Travelling Salesman Problem
 

Dongmei Xiao^1,3, Wenxia Li^2,3*, Lin He^3
1Department of Mathematics, Shanghai Jiao Tong University, Shanghai 200030, (P.R.CHINA)
²Department of Mathematics, East China Normal University, Shanghai 200062, (P.R.CHINA)
³Bio-X DNA Computer Consortium, Shanghai Jiao Tong University,
Shanghai 200030, (P.R.CHINA)

In this paper, we consider DNA procedures and algorithms for solving the travelling salesman problem and the generalized travelling salesman problem in the Adleman-Lipton model. The procedures work in O(n2) biological operations for the (generalized) travelling salesman problems of an edge-weighted graph with n vertices.