|
|
 |
| |
|
|
|
Fast parallel algorithm to the minimum edge cover problem based on DNA molecular computation |
|
|
|
PP: 711-716 |
|
|
|
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 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. |
|
|
|
|
|
|
|
