Artículo
A uniform family of tissue P systems with cell division solving 3-COL in a linear time
Autor/es | Díaz Pernil, Daniel
Gutiérrez Naranjo, Miguel Ángel Pérez Jiménez, Mario de Jesús Riscos Núñez, Agustín |
Departamento | Universidad de Sevilla. Departamento de Ciencias de la Computación e Inteligencia Artificial |
Fecha de publicación | 2008 |
Fecha de depósito | 2017-12-26 |
Publicado en |
|
Resumen | Several examples of the efficiency of cell-like P systems regarding the solution of NPcomplete
problems in polynomial time can be found in the literature(obviously, trading
space for time). Recently, different new models ... Several examples of the efficiency of cell-like P systems regarding the solution of NPcomplete problems in polynomial time can be found in the literature(obviously, trading space for time). Recently, different new models of tissue-like P systems have received much 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. |
Agencias financiadoras | Ministerio de Educación y Ciencia (MEC). España Junta de Andalucía |
Identificador del proyecto | TIN2005-09345-C04-01
TIC-581 |
Cita | Díaz Pernil, D., Gutiérrez Naranjo, M.Á., Pérez Jiménez, M.d.J. y Riscos Núñez, A. (2008). A uniform family of tissue P systems with cell division solving 3-COL in a linear time. Theoretical Computer Science, 404 (1-2), 76-87. |
Ficheros | Tamaño | Formato | Ver | Descripción |
---|---|---|---|---|
QDQE=&response-content-disposi ... | 1.459Mb | [PDF] | Ver/ | |