Solving minimum k-center problem in the Adleman-Lipton model

Saeed Safaei*, Hajar Mozaffar, Babak Esmaeili

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract / Description of output

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.

Original languageEnglish
Title of host publicationProceedings of the 2008 International Conference on Foundations of Computer Science, FCS 2008
Pages251-255
Number of pages5
Publication statusPublished - 1 Dec 2008
Event2008 International Conference on Foundations of Computer Science, FCS 2008 - Las Vegas, NV, United States
Duration: 14 Jul 200817 Jul 2008

Publication series

NameProceedings of the 2008 International Conference on Foundations of Computer Science, FCS 2008

Conference

Conference2008 International Conference on Foundations of Computer Science, FCS 2008
Country/TerritoryUnited States
CityLas Vegas, NV
Period14/07/0817/07/08

Keywords / Materials (for Non-textual outputs)

  • Adleman-Lipton model
  • Minimum k-center problem
  • NP complete

Fingerprint

Dive into the research topics of 'Solving minimum k-center problem in the Adleman-Lipton model'. Together they form a unique fingerprint.

Cite this