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

Ardashir Dolati*, M. S. Haghighat, Saeed Safaei, Hajar Mozaffar

*Corresponding author for this work

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

Abstract

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.

Original languageEnglish
Title of host publicationProceedings of the 2008 International Conference on Foundations of Computer Science, FCS 2008
Pages97-101
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

  • Adleman-Lipton model
  • Minimum Β-vertex separator problem

Fingerprint

Dive into the research topics of 'Solving minimum Β-vertex separator problems in the Adleman-Lipton model'. Together they form a unique fingerprint.

Cite this