Solving the Maximum Weighted Clique Problem Based on Parallel Biological Computing Model

Abstract EN

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.