Hybrid-Based DNA Solution to the Vertex Cover Problem
For an undirected graph G =(V, E) and a positive integer k, k≤|V |, a vertex cover is a vertex subset V(∈)V of satisfying that each edge in E is incident to at least one vertex in it, and the vertex cover problem is to find a vertex cover of size k. We give a hybrid-based DNA solution to the vertex cover problem by means of a polynomial transformation from the vertex cover problem to the Hamiltonian circle problem. The cover subgraphs of the edges in G are first constructed and then they are linked with k selection vertices through the following method: The cover subgraphs of the edges incident to one vertex are linked together to form a subpath by edge set Evi=< (vi, evij, 4), (vi, evij+1, 1)>|1≤I≤n, 1≤j＜deg(vi); each selection vertex as is linked to each start point and end point of each subpath by edge set Eas=<as, (vi, evi1, 1)>, <as, (vi, evideg(vi)-1, 4)>|1≤s≤k, 1≤i<n. The obtained graph G＇ has a Hamiltonian circle if and only if the given graph G has a vertex cover of size k. Thus, we present a DNA solution to the vertex cover problem based on the DNA solution to Hamiltonian circle problem. Just as other arithmetical operations are implemented through converting them into addition operation in computer, the proposed DNA solution to the vertex cover problem provides an important foundation for DNA computing and has the characteristics of easy encoding and simple implementation.
DNA computing, hybridization, DNA encoding method, algorithm combinatorial optimization, vertex cover
Aili Han Daming Zhu
School of Computer Science and Technology, Shandong University, and the Department of Computer Scien School of Computer Science and Technology, Shandong University, Jinan 250061 China.
国际会议
武汉
英文
2007-09-21（万方平台首次上网日期，不代表论文的发表时间）