A DNA procedure for solving the shortest path problem

作者：Wang, Zhaocai; Xiao, Dongmei; Li, Wenxia^*; He, Lin

来源：Applied Mathematics and Computation, 2006, 183(1): 79-84.

DOI：10.1016/j.amc.2006.05.061

• the shortest path problem
• NP-complete problem
• Adleman-Lipton model
• DNA computing

In this paper, we consider a procedure for solving the shortest path problem in the Adleman-Lipton model. The procedure works in O(n) steps for the shortest path problem of an edge-weighted graph with n vertices.

• 出版日期2006-12-1
• 单位上海交通大学; 华东师范大学