DNA Solution of the Maximal Clique Problem

See allHide authors and affiliations

Science  17 Oct 1997:
Vol. 278, Issue 5337, pp. 446-449
DOI: 10.1126/science.278.5337.446

You are currently viewing the abstract.

View Full Text


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.

View Full Text