




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

PP: 711716 

Author(s) 

Zhaocai Wang,
Dongmei Huang,
Chengpei Tang,


Abstract 

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 NPcomplete 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 NPcomplete continuous path search problems (for
example HPP, travelling salesman problem), rarely for NPhard 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
NPcomplete problem. 




