A uniform family of tissue P systems with cell division solving 3-COL in a linear time

Mon, 10/20/2008 - 12:11 — mmartinez

Title	A uniform family of tissue P systems with cell division solving 3-COL in a linear time
Publication Type	Journal Papers
Year of Publication	2008
Authors	Díaz-Pernil, D., Gutiérrez-Naranjo M. A., Pérez-Jiménez M. J., & Riscos-Núñez A.
Journal Title	Theoretical Computer Science
Publisher	Elsevier
Place Published	Amsterdam (The Netherlands)
Volume	404
Pages	76-87
Date Published	09/2008
Abstract	Several examples of the efficiency of cell-like P systems regarding the solution of NP-complete 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.
Keywords	Membrane computing; Tissue P systems; Cell division; 3-coloring problem
URL	http://dx.doi.org/10.1016/j.tcs.2008.04.005
Issue	1-2
Impact Factor	0.806
Ranking	51/84 - Q3
ISSN Number	0304-3975
DOI	10.1016/j.tcs.2008.04.005

Research Group on Natural Computing