%0 Generic
%D 2008
%T A uniform family of tissue P systems with cell division solving 3-COL in a linear time
%A Daniel Díaz-Pernil
%A Miguel A. Gutiérrez-Naranjo
%A Mario J. Pérez-Jiménez
%A Agustín Riscos-Núñez
%C Amsterdam (The Netherlands)
%I Elsevier
%K Membrane computing; Tissue P systems; Cell division; 3-coloring problem
%N 1-2
%P 76-87
%R 10.1016/j.tcs.2008.04.005
%U http://dx.doi.org/10.1016/j.tcs.2008.04.005
%V 404
%X 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.
%8 09/2008