화학공학소재연구정보센터
Science, Vol.278, No.5337, 446-449, 1997
DNA Solution of the Maximal Clique Problem
The maximal clique problem has been solved by means of molecular biology techniques. A pool of DNA molecules corresponding to the total ensemble of six-vertex cliques was built, followed by a series of selection processes. The algorithm is highly parallel and has satisfactory fidelity. This work represents further evidence for the ability of DNA computing to solve NP-complete search problems.