We found a match
Your institution may have rights to this item. Sign in to continue.
- Title
Solving the Maximum Weighted Clique Problem Based on Parallel Biological Computing Model.
- Authors
Wang, Zhaocai; Qin, Jiangfeng; Ji, Zuwen; Huang, Dongmei; Li, Lei
- Abstract
The maximum weighted clique (MWC) problem, as a typical NP-complete problem, is difficult to be solved by the electronic computer algorithm. The aim of the problem is to seek a vertex clique with maximal weight sum in a given undirected graph. It is an extremely important problem in the field of optimal engineering scheme and control with numerous practical applications. From the point of view of practice, we give a parallel biological algorithm to solve the MWC problem. For the maximum weighted clique problem with m edges and n vertices, we use fixed length DNA strands to represent different vertices and edges, fully conduct biochemical reaction, and find the solution to the MVC problem in certain length range with O(n2) time complexity, comparing to the exponential time level by previous computer algorithms. We expand the applied scope of parallel biological computation and reduce computational complexity of practical engineering problems. Meanwhile, we provide a meaningful reference for solving other complex problems.
- Subjects
PARALLEL computers; BIOLOGICAL models; COMPUTER algorithms; BIOMEDICAL engineering; UNDIRECTED graphs; GEOMETRIC vertices
- Publication
Mathematical Problems in Engineering, 2015, Vol 2015, p1
- ISSN
1024-123X
- Publication type
Article
- DOI
10.1155/2015/275019