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

Content
 

Volumes > Volume 08 > No. 5

 
   

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.

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