Title :
DNA Algorithm Based on Incomplete Molecule Commixed Encoding for the Shortest Path Problem
Author :
Wang, Qing-Hu ; Pei, Zhi-Li ; Hou, Xiu-Ping ; Sun, Qi ; Zheng, Hong
Author_Institution :
Coll. of Comput. Sci. & Eng., Changchun Univ. of Technol., Changchun, China
Abstract :
DNA algorithms have solved some NP-complete problems such as Hamilton path and Chinese postman problem; however there are only some suggestions for the shortest path problem. Weight encoding is a very important and challenge aspect in DNA computing. In this paper a computing method which based on incomplete Molecule Commixed Encoding (IMCE) is proposed. In this method, the vertex of the graph is encoded as single-strand, weight is encoded as double-strands and the edge is incomplete encoded. This method is used to solve the shortest path problem.
Keywords :
biocomputing; computational complexity; encoding; graph theory; Chinese postman problem; DNA algorithm; DNA computing; Hamilton path; NP-complete problems; graph theory; incomplete molecule commixed encoding; shortest path problem; weight encoding; Biological information theory; Biological system modeling; Biology computing; Computer science; DNA computing; Educational institutions; Encoding; Information science; Parallel processing; Shortest path problem;
Conference_Titel :
Information Science and Engineering (ICISE), 2009 1st International Conference on
Conference_Location :
Nanjing
Print_ISBN :
978-1-4244-4909-5
DOI :
10.1109/ICISE.2009.516
