Efficient DNA sticker algorithms for NP-complete graph problems

doi:10.1016/S0010-4655(02)00270-9

Return

Efficient DNA sticker algorithms for NP-complete graph problems

2002-04-01

PRE

Zimmermann, KH *

DOI：10.1016/S0010-4655(02)00270-9

Original

Original request for help

Save

Abstract

En 中文

Adleman's successful solution of a seven-vertex instance of the NP-complete Hamiltonian directed path problem by a DNA algorithm initiated the field of biomolecular computing. We provide DNA algorithms based on the sticker model to compute all k-cliques, independent k-sets, Hamiltonian paths, and Steiner trees with respect to a given edge or vertex set. The algorithms determine not merely the existence of a solution but yield all solutions (if any). For an undirected graph with n vertices and m edges, the running time of the algorithms is linear in n + m. For this, the sticker algorithms make use of small combinatorial input libraries instead of commonly used large libraries. The described algorithms are entirely theoretical in nature. They may become very useful in practice, when further advances in biotechnology lead to an efficient implementation of the sticker model. (C) 2002 Elsevier Science B.V. All rights reserved.

Keywords:

DNA

molecular computing

sticker model

graph theory

clique

independent set

hamiltonian path

steiner tree

AI Summary

Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.