Dissemin is shutting down on January 1st, 2025

Published in

American Chemical Society, Journal of Chemical Information and Modeling, 3(42), p. 524-528

DOI: 10.1021/ci010016o

Links

Tools

Export citation

Search in Google Scholar

DNA Solution of a Graph Coloring Problem

Journal article published in 2002 by Yachun Liu, Jin Xu, Linqiang Pan ORCID, Shiying Wang
This paper is available in a repository.
This paper is available in a repository.

Full text: Download

Green circle
Preprint: archiving allowed
  • Must obtain written permission from Editor
  • Must not violate ACS ethical Guidelines
Upload
Orange circle
Postprint: archiving restricted
  • Must obtain written permission from Editor
  • Must not violate ACS ethical Guidelines
Upload
Red circle
Published version: archiving forbidden
Policy details
Data provided by SHERPA/RoMEO

Abstract

The graph-theoretic parameter that has probably received the most attention over the years is the chromatic number. As is well-known, the coloring problem is an NP-Complete problem. In this paper, it has been solved by means of molecular biology techniques. The algorithm is highly parallel and has satisfactory fidelity. This work shows further evidence for the ability of DNA computing to solve NP-Complete problems.