TY - GEN

T1 - Solving minimum Β-vertex separator problems in the Adleman-Lipton model

AU - Dolati, Ardashir

AU - Haghighat, M. S.

AU - Safaei, Saeed

AU - Mozaffar, Hajar

PY - 2008/12/1

Y1 - 2008/12/1

N2 - In recent works for high-performance computing, computation with DNA molecules, i.e. DNA computing, has considerable attention as one of non-silicon-based computing. Watson-Crick complementarity and massive parallelism are two important features of DNA. Using the features, one can solve an NP-complete problem, which usually needs exponential time on a silicon-based computer, in a polynomial number of steps with DNA molecules. In this paper, we consider a procedure for solving minimumß-vertex separator problems in the Adleman - Lipton model. The procedure works in O(n 2) steps for minimum ß-vertex separator problems of an undirected graph with n vertices.

AB - In recent works for high-performance computing, computation with DNA molecules, i.e. DNA computing, has considerable attention as one of non-silicon-based computing. Watson-Crick complementarity and massive parallelism are two important features of DNA. Using the features, one can solve an NP-complete problem, which usually needs exponential time on a silicon-based computer, in a polynomial number of steps with DNA molecules. In this paper, we consider a procedure for solving minimumß-vertex separator problems in the Adleman - Lipton model. The procedure works in O(n 2) steps for minimum ß-vertex separator problems of an undirected graph with n vertices.

KW - Adleman-Lipton model

KW - Minimum Β-vertex separator problem

UR - http://www.scopus.com/inward/record.url?scp=62649126156&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:62649126156

SN - 9781601320667

T3 - Proceedings of the 2008 International Conference on Foundations of Computer Science, FCS 2008

SP - 97

EP - 101

BT - Proceedings of the 2008 International Conference on Foundations of Computer Science, FCS 2008

T2 - 2008 International Conference on Foundations of Computer Science, FCS 2008

Y2 - 14 July 2008 through 17 July 2008

ER -