A linear-time tissue P system based solution for the 3-coloring problem
Wed, 10/17/2007 - 10:47 — ana
| Title | A linear-time tissue P system based solution for the 3-coloring problem |
| Publication Type | Journal Papers |
| Year of Publication | 2007 |
| Authors | Díaz-Pernil, D., Gutiérrez-Naranjo M. A., Pérez-Jiménez M. J., & Riscos-Núñez A. |
| Journal Title | Electronic Notes in Theoretical Computer Science |
| Publisher | Elsevier B.V. |
| Volume | 171 |
| Pages | 81-93 |
| Abstract | In the literature, several examples of the efficiency of cell-like P systems regarding the solution of NP-complete problems in polynomial time can be found (obviously, trading space for time). Recently, different new models of tissue-like P systems have received important attention from the scientific community. In this paper we present a linear-time solution to an NP-complete problem from graph theory, the 3-coloring problem, and we discuss the suitability of tissue-like P systems as a framework to address the efficient solution to intractable problems. |
| Keywords | 3-coloring problem, cell division, Membrane computing, Tissue P Systems |
| URL | http://dx.doi.org/10.1016/j.entcs.2007.05.009 |
| Issue | 2 |
| DOI | 10.1016/j.entcs.2007.05.009 |
Research Group on Natural Computing (PAI - TIC 193)
Department of Computer Science and Artificial Intelligence
University of Seville
Webmasters: the members of the RGNC
| Follow us: |  |
 |
|
Featured News: |