@article {355, title = {A uniform family of tissue P systems with cell division solving 3-COL in a linear time}, journal = {Theoretical Computer Science}, volume = {404}, year = {2008}, month = {09/2008}, pages = {76-87}, publisher = {Elsevier}, address = {Amsterdam (The Netherlands)}, 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}, issn = {0304-3975}, doi = {10.1016/j.tcs.2008.04.005 }, url = {http://dx.doi.org/10.1016/j.tcs.2008.04.005}, author = {Daniel D{\'\i}az-Pernil and Miguel A. Guti{\'e}rrez-Naranjo and Mario J. P{\'e}rez-Jim{\'e}nez and Agust{\'\i}n Riscos-N{\'u}{\~n}ez} }