TY - GEN
T1 - Solving minimum k-center problem in the Adleman-Lipton model
AU - Safaei, Saeed
AU - Mozaffar, Hajar
AU - Esmaeili, Babak
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 k-center problem in the Adleman-Lipton model. The procedure works in O(n 2) steps for minimum k-center problem of a directed 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 k-center problem in the Adleman-Lipton model. The procedure works in O(n 2) steps for minimum k-center problem of a directed graph with n vertices.
KW - Adleman-Lipton model
KW - Minimum k-center problem
KW - NP complete
UR - http://www.scopus.com/inward/record.url?scp=62649174152&partnerID=8YFLogxK
M3 - Conference contribution
AN - SCOPUS:62649174152
SN - 1601320663
SN - 9781601320667
T3 - Proceedings of the 2008 International Conference on Foundations of Computer Science, FCS 2008
SP - 251
EP - 255
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 -