Improved algorithm for solving the maximal clique problem with DNA computing

H. Aoyagi, N. Rajaee, O. Ono

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

Abstract

In this paper, we improve an algorithm proposed by Q. Ouyang to solve a maximal clique problem. While we can determine the size of the largest clique by sorting the length of the DNA strands in Q. Ouyang proposal, we cannot determine the exact vertices involved in the maximal clique. Thus in our improved algorithm, the exact vertices for each clique can be derived straightforwardly from the read-out in the gel electrophoresis process.

Original languageEnglish
Title of host publicationProceedings of the 15th International Symposium on Artificial Life and Robotics, AROB 15th'10
Pages713-714
Number of pages2
Publication statusPublished - 1 Dec 2010
Event15th International Symposium on Artificial Life and Robotics, AROB '10 - Beppu, Oita, Japan
Duration: 4 Feb 20106 Feb 2010

Publication series

NameProceedings of the 15th International Symposium on Artificial Life and Robotics, AROB 15th'10

Conference

Conference15th International Symposium on Artificial Life and Robotics, AROB '10
CountryJapan
CityBeppu, Oita
Period4/02/106/02/10

    Fingerprint

Keywords

  • DNA computing
  • The maximal clique problem
  • The parallel overlap assembly

Cite this

Aoyagi, H., Rajaee, N., & Ono, O. (2010). Improved algorithm for solving the maximal clique problem with DNA computing. In Proceedings of the 15th International Symposium on Artificial Life and Robotics, AROB 15th'10 (pp. 713-714). (Proceedings of the 15th International Symposium on Artificial Life and Robotics, AROB 15th'10).