| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 4629568 | Applied Mathematics and Computation | 2012 | 4 Pages |
Abstract
The traveling salesman problem is to find a minimum cost (weight) path for a given set of cities (vertices) and roads (edges). The path must start at a specified city and end there after going through all the other given cites only once. It is a classical NP-complete problem in graph theory. In this paper, we consider a DNA procedure for solving the traveling salesman problem in the Adleman–Lipton model. The procedure works in O(n)O(n) steps for the traveling salesman of an edge-weighted graph with n vertices.
Keywords
Related Topics
Physical Sciences and Engineering
Mathematics
Applied Mathematics
Authors
Zhaocai Wang, Yiming Zhang, Weihua Zhou, Haifeng Liu,