|
|
 |
| |
|
|
|
Solving the Maximum Independent Set Problem based on Molecule Parallel Supercomputing |
|
|
|
PP: 2361-2366 |
|
|
|
Author(s) |
|
|
|
Zhaocai Wang,
Jian Tan,
Lanwei Zhu,
Wei Huang,
|
|
|
|
Abstract |
|
|
| The maximum independent set Problem is to find a biggest vertex independent set in a given undirected graph. It is a vitally
important NP problem in graph theory and applied mathematics, having numerous real life applications. It can be difficultly solved by
the electronic computer in exponential level time. Simultaneity in previous studies DNA molecular computation usually be used to solve
NP-complete continuous path search problems (for example HPP, traveling salesman problem), rarely for NP problems with discrete
vertex or path solutions result, such as the maximum independent set problem, graph coloring problem and so on. In this paper, we
present a new algorithm for solving the maximum independent set problem with DNA molecular operations. For an undirected graph
with n vertices, We reasonably design fixed length DNA strands representing the vertices and edges of graph, take appropriate steps
and get the solutions of the problem in proper length range using O(n2) time. We extend the application of DNA molecular operations
and simultaneity simplify the complexity of the computation. |
|
|
|
|
|
|
|
