%0 Generic
%D 2007
%T A linear-time tissue P system based solution for the 3-coloring problem
%A Daniel Díaz-Pernil
%A Miguel A. Gutiérrez-Naranjo
%A Mario J. Pérez-Jiménez
%A Agustín Riscos-Núñez
%I Elsevier B.V.
%K 3-coloring problem
%K cell division
%K Membrane computing
%K Tissue P Systems
%N 2
%P 81-93
%R 10.1016/j.entcs.2007.05.009
%U http://dx.doi.org/10.1016/j.entcs.2007.05.009
%V 171
%X 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.