Login New user?  
01-Applied Mathematics & Information Sciences
An International Journal


Volumes > Volume 7 > No. 2L


Fast parallel algorithm to the minimum edge cover problem based on DNA molecular computation

PP: 711-716
Zhaocai Wang, Dongmei Huang, Chengpei Tang,
The minimum edge cover (MEC) problem is to find a smallest edge subset in a given undirected and simple graph, that every vertice in the graph at least belongs to one edge of the subset. It is a vitally important NP-complete problem in theory of computation and applied mathematics, having numerous real life applications. It can be difficultly solved by the electronic computer in exponential level time. In previous studies DNA molecular operations usually be used to solve NP-complete continuous path search problems (for example HPP, travelling salesman problem), rarely for NP-hard problems with discrete vertices or edges solutions result, such as the minimum edge cover problem, graph colouring problem and so on. In this paper, we present a DNA algorithm for solving the MEC problem with DNA molecular operations. For an undirected and simple graph with n vertices and m edges, we reasonably design fixed length DNA strands representing vertices and edges of the graph, take appropriate steps and get the solutions of the MEC problem in proper length range using O(n2) time. We theoretically proved the algorithm and simulate the DNA experiment to get correct solution of the ensample. We extend the application of DNA molecular operations and simultaneity simplify computational complexity of NP-complete problem.

  Home   About us   News   Journals   Conferences Contact us Copyright naturalspublishing.com. All Rights Reserved